Semi-Fibonacci Partitions
![](/img/demonstrations-branding.png)
Requires a Wolfram Notebook System
Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.
This Demonstration counts the number of partition subsum polynomials without repeated roots.
[more]
Contributed by: George Beck (July 2019)
Open content licensed under CC BY-NC-SA
Snapshots
Details
Definitions
,
and if
is a partition of
with one odd part, say
, define:
.
If is a set of partitions, define
,
, and if
contains only partitions with one odd part,
.
This defines the semi-Fibonacci partitions of :
,
,
.
Then ,
,
,
,
, ….
Lemma 1
The roots of are
,
.
Proof
First check the roots: . Now check the roots are distinct: Suppose
,
, and
. Then
. Since
,
, so
. Therefore the
are distinct and are the
roots of
. \[FilledSquare]
Lemma 2
The polynomials and
have a common root iff
and
are both odd, in which case there are
common roots. Therefore the polynomials have no common root iff
is odd.
Proof
If the two polynomials have a common root, then there are integers and
,
,
such that
so
. Therefore
, which implies that the highest powers of 2 dividing
and
are equal, so that
and
are both odd.
If and
are both odd, let
and
be such that
and
. Then
so
, which gives a common root of the two polynomials.
Suppose and
have a common root. Let
and
. Then the equations
and
also have a common root, say
. Then with
,
, so
is also a solution of
and likewise of
.
For the last statement, and
cannot both be even—the GCD would absorb the 2. So the polynomials have no common root iff one of
or
is odd and the other even, or, equivalently,
is odd. \[FilledSquare]
Lemma 3
The polynomial has no repeated root iff
is odd for each pair of parts
,
of
.
Proof
Apply lemma 2 to the definition . \[FilledSquare]
Lemma 4
If , then
has only even parts.
If
, then
has exactly one odd part.
In the definition
, the union is disjoint.
Proof
The parts of a partition in are clearly all even.
For induction, assume each partition in has at exactly one odd part; this is true for the base case
. Suppose
for some
. Since
has at most one odd part, the same is true for
. Suppose
for some
. Since
has no odd parts,
has exactly one odd part, namely 1.
The union is disjoint because the odd parts of are all 1 and the odd parts of
are all greater than 1. \[FilledSquare]
Lemma 5
iff for each pair of parts
and
of
,
is odd.
Proof
This is vacuously true for the partitions with one part, . For induction, assume the statement is true up to
.
If is even and
, then
is odd by the induction hypothesis, so the condition holds for 2
.
If is odd and
, either there is a
such that
or there is a
such that
. In the first case, there is only one new part, 1; because
and all the other parts are even,
is odd. In the second case, by lemma 4,
has exactly one odd part, so
is odd and the others follow by induction, since the even parts belonged to partitions in
. \[FilledSquare]
Lemma 6
.
Proof
For induction, the base case is
. By definition of
,
. By lemma 4, since the union is disjoint,
. Therefore
satisfies the same conditions as
and they are the same sequence. \[FilledSquare]
Theorem
The number of partitions for which
has no repeated root is the semi-Fibonacci sequence.
Proof
By lemma 3, has no repeated root iff
is odd for each pair of parts
,
of
. By lemma 5, the latter statement is equivalent to
. By lemma 6, the number of
with no repeated root is counted by
. \[FilledSquare]
References
[1] N. J. A. Sloane "A000009." The On-Line Encyclopedia of Integer Sequences. https://oeis.org/A000009.
[2] N. J. A. Sloane "A126796." The On-Line Encyclopedia of Integer Sequences. https://oeis.org/A126796.
[3] N. J. A. Sloane "A030067." The On-Line Encyclopedia of Integer Sequences. https://oeis.org/A030067.
Permanent Citation