16
$\begingroup$

Let $F_i$ denote the $i$th Fibonacci number (with $F_1=F_2=1$). Define $$ P_n(x) = \prod_{i=1}^n (1+x^{F_{i+1}}). $$ Let $\nu_k(n)$ denote the number of coefficients of the polynomial $P_n(x)$ that are equal to the positive integer $k$. Evidence suggests that for sufficiently large $n$ (depending on $k$), $\nu_k(n)$ is a linear polynomial in $n$. These polynomials for $1\leq k\leq 12$ are empirically given by $2n$, $4n-8$, $8n-32$, $12n-68$, $16n-112$, $24n-192$, $24n-224$, $36n-352$, $40n-432$, $48n-544$, $40n-512$, and $88n-1056$. How can one prove these observations and generalize to any $k$? Similar conjectures can be made for a wide class of more general polynomials. See my papers https://arxiv.org/abs/1901.04647 and https://arxiv.org/abs/2101.02131 for some related results. The linear algebraic techniques in these papers might be applicable to the present problem.

Addendum. The case $k=1$ follows easily from properties of the Fibonacci triangle poset discussed in Section 3 of https://arxiv.org/abs/2101.02131.

Improve this question
$\endgroup$
3

2 Answers 2

Reset to default
5
$\begingroup$

I will use the set up of my answer to a previous question about "Fibonacci polynomials".

The key observation is that the coefficient of $x^m$ in $P(x)$ equals the number of "unrollings" of the Zeckendorf representation $Z_m$ (viewed as a $01$-string) of $m$, where any substring $001$ can be unrolled into $110$. Let $U(Z_m)$ denote the number of such unrollings. It is easy to see that $$U(0^p1v) = U(v) + \left\lfloor\frac{p}2\right\rfloor U(0v).$$

Then one can notice that $$\nu_k(n) = \nu'_k(n) + \nu'_k(n-1) - [k=1],$$ where $\nu'_k(n)$ is the number of coefficients of $x^m$ in $P(x)$ equal $k$ with $m<F_{n+2}$ (ie. $|Z_m|\leq n$). Here the Iverson bracket $[k=1]$ eliminates double counting of $v=0^n$ and $v=0^{n-1}$, which both correspond to $m=0$ .

The aforementioned recurrence for $U$ allows us to obtain one for $\nu'_k(n)$ as follows.

Let $a_1(n,k)$ be the number of strings $v$ of length $n$ starting with 0 such that $U(v)=k$, and let $a_2(n,k_1,k_2)$ be the number of strings $v$ of length $n$ starting with 0 such that $U(v)=k_1$ and $U(0v)=k_2$. Clearly, $a_2(n,k_1,k_2)=0$ whenever $k_1>k_2$ and we find it convenient to assume that both $a_1$ and $a_2$ are zero for $n<0$. Then we have $$\nu'_k(n) = a_1(n,k) + a_1(n-1,k),$$ where the terms enumerate $v$ starting with 0 and 1, respectively. The count $a_1$ satisfies the recurrence: \begin{split} a_1(n,k) &= [k=1] + a_1(n-2,k) \\ &+ \sum_{p=2}^{2k-1} \sum_{k_2 = \lceil k/(1+c_p)\rceil}^{\lfloor (k-1)/c_p\rfloor} a_2(n-1-p,k-c_pk_2,k_2), \end{split} where $p$ runs over the possible lengths of the initial run of 0's in $v$, the first term corresponds to $v=0^n$ and the second term corresponds to $p=1$, and $c_p:=\left\lfloor\frac{p}2\right\rfloor$. Finally, the count $a_2$ satisfies the recurrence: \begin{split} &a_2(n,k_1,k_2) = [(k_1,k_2)=(1,1)] \\ &+ [k_1=k_2]\cdot\sum_{c=1}^{k_1-1} \sum_{t = \lceil k_1/(1+c)\rceil}^{\lfloor (k_1-1)/c\rfloor} a_2(n-1-2c,k_1-ct,t) \\ & + [k_1<k_2]\cdot a_2(n-1-(2\lfloor \tfrac{k_1-1}{k_2-k_1}\rfloor+1), (k_1-1) \bmod (k_2-k_1) + 1,k_2-k_1), \end{split} where the terms correspond to $v=0^n$, even $p>0$, and odd $p>0$, respectively.

Example $k=1$. In this case we have $a(n,1) = 1 + a_1(n-2,1)$, implying that $a_1(n,1)=1+\left\lfloor\frac{n}2\right\rfloor$. Then $a_2(n,0,1) = 0$ and $a_2(n,1,1) = 1$. It follows that $\nu'_1(n) = n+1$ and $\nu_1(n) = 2n$.

ADDED. It can be seen that $a_2(n,k_1,k_2)$ stabilizes as $n$ grows and its limit $\bar a_2(k_1,k_2)$ satisfies the recurrence: \begin{split} &\bar a_2(k_1,k_2) = [(k_1,k_2)=(1,1)] \\ &+ [k_1=k_2]\cdot \sum_{c=1}^{k_1-1} \sum_{t = \lceil k_1/(1+c)\rceil}^{\lfloor (k_1-1)/c\rfloor} \bar a_2(k_1-ct,t) \\ & + [k_1<k_2]\cdot \bar a_2( (k_1-1) \bmod (k_2-k_1) + 1, k_2-k_1). \end{split} Then it is easy to find the coefficient $q_k$ of $n$ in the linear formula for $\nu_k(n)$ (which is the quadruple of such coefficient in $a_1(n,k)$) as $$q_k = 2[k=1] + 4\sum_{c=1}^{k-1} \sum_{k_2 = \lceil k/(1+c)\rceil}^{\lfloor (k-1)/c\rfloor} \bar a_2(k-ck_2,k_2).$$ Here are the values of $q_k$ for $k\leq 30$:

2, 4, 8, 12, 16, 24, 24, 36, 40, 48, 40, 88, 48, 72, 96, 108, 64, 152, 72, 176, 144, 120, 88, 312, 144, 144, 200, 264, 112, 416

There seems to be no easier way to get the free term of $\nu_k(n)$ than computing it as $\nu_k(n) - q_kn$ for large enough $n$.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ This is an excellent solution. There should be more general results for which a different method is needed. One random example: define $G_0=1$, $G_1=3$, $G_i=2G_{i-1}+2G_{i-2}$ for $i\geq 2$. Let $P_n(x) = \prod_{i=0}^{n-1} \left(1+x^{G_i}+x^{2G_i}\right)$. Let $f_k(n)$ be the number of coefficients of $P_n(x)$ equal to $k$. Then empirically $\sum_{n\geq 0}f_1(n)x^n = (1+x^2)/(1-x)(1-2x-x^2)$, $\sum_{n\geq 0}f_2(n)x^n = 2x^3(1+x)^2/(1-2x-x^2)^2$, etc. $\endgroup$ Commented Sep 22, 2022 at 15:35
4
$\begingroup$

This is just a `formulas-free' version of the proof that the numbers $\nu_k(n)$ are indeed linear in $n$, for a fixed $k$ and large enough $n\geq n_0(k)$. The following lemma is the same as Max Alekseyev's starting point. As in his answer, we assume that the Zeckendorf representation is a $01$-string, where the leftmost digit is the least impotrant one.

Lemma. Each representation of a positive integer $M$ as a sum of distinct Fibonacci numbers is obtained from the Zeckendorf representation of $M$ by unrollings of the form $001\mapsto 110$.

Proof. Clearly, all unrollings produce representations of $M$.

Conversely, we show that each representation (also viewed as a $01$-string) can be rolled to the Zeckendorf representation by the operations $110\mapsto 001$. Take an arbitrary representation. Find the rightmost occurrence of $11$; it is followed by $0$ (or by the end of line, in which case we just augment the string by $0$ on the right). Replace this $110$ with $001$ and repeat.

This process stops, as the sum of elements in the string decreases. At the end, we get a string without occurrences of $11$, i.e., the Zeckendorf representation of $M$. $\Box$

Now let the Zeckendorf representation of $M$ have the form $0^{i_p}10^{i_{p-1}}1\dots 0^{i_1}1$, where $i_p\geq 0$ and $i_t>0$ for $1\leq t<p$. Assume that $M$ has exactly $k$ representations.

1. We have $i_t\leq 2k-1$ for all $t$. Indeed, if $i:=i_t\geq 2k$, then we can make the sequence of unrollings $$ 0^i1\mapsto 0^{i-2}110\mapsto 0^{i-4}11010\mapsto\dots\mapsto 0^{i-2k}1(10)^k, $$ obtaining $k+1$ distinct representations, which cannot appear.

2. We have $i_t\leq1$ for all $t\geq k$ (thus $i_t=1$ for $p<t\leq k$ and $i_p\in\{0,1\}$ if $p\geq k$). Indeed, if $i_t>1$, then we can successively unroll the $t$th rightmost $1$, then the $(t-1)$th rightmost $1$, and so on, again obtaining at least $k+1$ distinct representations.

The two properties above show that the Zeckendorf representations of all numbers $M$ under consideration look like either $0101\dots01 $ or $1010\dots 1$ followed by a tail with bounded number of $1$s and bounded number of $0$s between consecutive $1$s. Moreover, the number of representations of such tail is still $n$, as the unrollings cannot touch the starting periodical part. There are finitely many such tails.

In other words, $\nu_k(n)$ can be computed as follows. There are finitely many possible tails corresponding to numbers having $k$ representations and having the form $10^{i_p}1\dots 0^{i_1}1$, where $i_k\geq 2$. Each of those can be augmented by a periodic string of the form $\dots 01010$. in order to produce a string of length at most $n$. The number of such strings is $\nu_k(n)$.

Now it is clear that this number is linear in $n$ for all sufficiently large $n\geq n_0$ (where $n_0$ is the largest length of the tail).

Improve this answer
$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.