A rational function related to Fibonacci numbers

Question

Let $F_n$ denote a Fibonacci number ($F_1=F_2=1$, $F_{n+1}=F_n+F_{n-1}$ for $n\geq 2$). Define $$\prod_{k=1}^n (1+x^{F_{k+1}}) = \sum_j f(n,j)x^j. $$ For a positive integer $r$ let $$ v_r(n) = \sum_j f(n,j)^r $$ and $$ V_r(x) = \sum_{n\geq 0} v_r(n)x^n. $$ It can be shown that $V_r(x)$ is a rational function. For instance, \begin{eqnarray*} V_1(x) & = & \frac{1}{1-2x}\\ V_2(x) & = & \frac{1-2x^2}{1-2x-2x^2+2x^3}\\ V_3(x) & = & \frac{1-4x^2}{1-2x-4x^2+2x^3}\\ V_4(x) & = & \frac{1-7x^2-2x^4}{1-2x-7x^2-2x^4+2x^5}\\ V_5(x) & = & \frac{1-11x^2-20x^4}{1-2x-11x^2-8x^3-20x^4+10x^5}\\ V_6(x) & = & \frac{1-17x^2-88x^4-4x^6}{1-2x-17x^2-28x^3-88x^4+26x^5-4x^6+4x^7}\\ V_7(x) & = & \frac{1-26x^2-311x^4-84x^6} {1-2x-26x^2-74x^3-311x^4+34x^5-84x^6+42x^7}. \end{eqnarray*} Note that the numerator is the "even part" of the denominator. Is this true in general?

Other patterns can be discerned empirically, e.g., if $D_r(x)$ denotes the denominator of $V_r(x)$ then \begin{eqnarray*} D_{2s+1}(x) & = & c_sx^{2s+1} -2c_sx^{2s} +\cdots\ (\mathrm{for \ some}\ c_s>0)\\ D_{2s}(x) & = & d_sx^{2s+1} -d_sx^{2s} +\cdots\ (\mathrm{for \ some}\ d_s>0). \end{eqnarray*}

Addendum. Here is a generalization of the conjecture that the numerator of $V_r(x)$ is the even part of the denominator. For fixed $k\geq 1$ define $$ F_{i+1}^{(k)}=F_{i}^{(k)}+F_{i-1}^{(k)}+\cdots+F_{i-k+1}^{(k)}, $$ with initial conditions $F^{(k)}_{1}=F^{(k)}_{2}=\cdots =F^{(k)}_{k}=1$. Let $t$ be an indeterminate, and let $v_r^{(k)}(n,t)$ be the sum of the $r$th powers of the coefficients of the polynomial $\prod_{i=1}^n\left(1+tx^{F_{i+k-1}^{(k)}}\right)$. It can be shown (Theorem 5.3 of the above link) that $$ \sum_{n\geq 0} v^{(k)}_2(n,t)x^n = \frac{1-t^{k-1}(1+t^2)x^k} {1-(1+t^2)x-t^{k-1}(1+t^2)x^k+t^{k-1}(1+t^4)x^{k+1}}. $$ Note that the numerator is the "divisible by $k$" part of the denominator. I conjecture that this behavior persists for any $r$. For instance, I conjecture that $$ \sum_{n\geq 0} v^{(k)}_3(n,t)x^n =\frac{1-u(u+1)(t^3+1)x^k+u^3(t^3-1)^2x^{2k}} {D_3^{(k)}(t,x)}, $$ where $u=t^{k-1}$ and \begin{eqnarray*} D_3^{(k)}(t,x) & = & 1-(t^3+1)x-u(u+1)(t^3+1)x^k\\ & & +u(u+1)(t^6-t^3+1)x^{k+1} +u^3(t^3-1)^2x^{2k}\\ & & +u^3(t^3-1)(t^6-1)x^{2k+1}. \end{eqnarray*} Note also that the denominator exponents are congruent to $0$ or $1$ modulo $k$.

It is also natural to ask to what extent this type of behavior can be generalized.

Answer 1

$\let\eps\varepsilon$ Here is an answer to the original question, for usual Fibonacci numbers. I apologise for changing the notation; the standard arguments for $f$ will be $f(n,k)$.

1. Recall that $V_r(0)=1$ (and $V_r$ is a rational function). Under these assumptions, the desired claim holds if and only if $W_r=(1-V_r)/V_r$ is an odd function. The 'only if' part is clear. For the 'if' part, it suffices to notice that, multiplying an odd function by a non-odd polynomial, we get a non-even function.

Hence we need to show that $$ \frac{1-V_r(x)}{V_r(x)}=\frac{1-V_r(-x)}{V_r(-x)}, \quad \text{or, equivalently,} \quad (2V_r(x)-1)(2V_r(-x)-1)=1. \tag{$*$} $$

2. Now we come into combinatorics of the representations. Each representation of $k$ as a sum of distinct numbers of the form $F_{i+1}$, $1\leq i\leq n$, will be denoted as $$ k=\overline{\eps_n\eps_{n-1}\dots \eps_1}=\sum_{i=1}^n \eps_i F_{i+1}. $$

Given nonnegative integers $k$ and $n$, there is a greedy representation $G_n(k)$ of $k$ as a sum of distinct numbers of the form $F_{i+1}$ with $i\leq n$ obtained as follows. Take the maximal $i\leq n$ such that $F_{i+1}\leq k$, subtract $F_{i+1}$ from $k$ and apply the procedure to $k:=k-F_{i+1}$ and $n:=i-1$. If we come to $k=0$ at some stage, we get the desired representation, otherwise $k$ has no such representations at all. Moreover, all representations of $k$ are obtained from $G_n(k)$ by replacements of the form $\overline{100}\mapsto\overline{011}$ (apply reverse changes while it is possible).

Say that a representation $\overline{\eps_n\dots \eps_1}$ is normal if (i) it is Zeckendorf, i.e., it contains no $\overline{11}$; (ii) it starts with $\eps_n=1$; and (iii) it ends with a nonzero even number of zeroes, i.e., $\eps_1=\dots=\eps_{2\ell}=0$ and $\eps_{2\ell+1}=1$ for some positive integer $\ell$. For technical reasons, the empty representation of $k=0$ is also considered as normal.

Now, any greedy representation $G_n(k)$ can be split into three parts $G_n(k)=H_n(k)N_n(k)T_n(k)$: the head $H_n(k)$ consisting either of zeroes or of ones; the normal part $N_n(k)$ which is a normal representation of some number; and the tail $T_n(k)$ of one of the forms $\overline{0101\dots}$ or $\overline{1010\dots}$. Either of the three parts may be empty. This representation is unique whenever $N_n(k)$ is non-empty (we will deal with the empty normal part separately).

The reason for such partition is that the head and the tail have no influence on the number $f(n,k)$. For the head this is obvious: neither zeroes nor ones in the head part may change during the replacements. For the tail, if the last digit is $1$, it persists everywhere, so its removal causes no influence on the number of representations. If $G_n(k)$ finishes with an odd number of zeroes, the last zero will not be replaced, so it also can be removed harmlessly. By these two operations, we remove the whole tail.

Now let $\mathcal N_n$ be the set of all numbers $k$ whose greedy representations $G_n(k)$ are normal, and denote $$ N_r(x)=\sum_{n\geq 0} x^n\sum_{k\in \mathcal N_n}f(n,k)^r. $$

The greedy representations of all numbers $a$ with $f(n,a)>0$ are obtained from those in $N_n$ by augmenting a head and a tail. Knowing their sizes, we can add two possible heads (if the length is positive) and two possible tails (similarly). The numbers with empty normal part should be treated separately: we easily see that there are $2n$ such greedy representations of length $n$. All in all, this provides a relation $$ V_r(x)=(N_r(x)-1)(1+2x+2x^2+2x^3+\dots)^2+(1+2x+4x^2+6x^3+\dots) =N_r(x)\frac{(1+x)^2}{(1-x)^2}+\frac{1+x^2}{(1-x)^2}-\frac{(1+x)^2}{(1-x)^2} =N_r(x)\frac{(1+x)^2}{(1-x)^2}-\frac{2x}{(1-x)^2}. $$

3. [This part is magic for me, parhaps it has a more conceptual explanation...] Now the relation $(*)$ rewrites as $$ \left(2N(x)\frac{(1+x)^2}{(1-x)^2}-\frac{4x}{(1-x)^2}-1\right) \left(2N(-x)\frac{(1-x)^2}{(1+x)^2}+\frac{4x}{(1+x)^2}-1\right) =1, $$ which simplifies to $$ (2N_r(x)-1)(2N_r(-x)-1)=1. \tag{$**$} $$ So we need to check the same property for $N_r$.

4. The relation $(**)$ can be checked combinatorially. Indeed, writing $$ N_r(x)=N_r^+(x)+N_r^-(x), $$ where $N_r^+$ and $N_r^-$ are even and odd, respectively, we rewrite $(**)$ as $$ N_r^+(N_r^+-1)=(N_r^-)^2. \tag{$***$} $$

If $k_1\in \mathcal N_{n_1}$ and $k_2\in\mathcal N_{n_2}$, let $k=\overline{G_{n_1}(k_1)G_{n_2}(k_2)}\in \mathcal N_{n_1+n_2}$. Clearly, this concatenation is $G_{n_1+n_2}(k)$, and any replacements of the form $\overline{100}\mapsto \overline{011}$ are performed only in one part (since $G_{n_1}(k_1)$ ends with an even number of zeroes). Therefore, $f(n_1,k_1)f(n_2,k_2)=f(n_1+n_2,k)$.

Moreover, if $G_n(k)$ is normal, it splits into minimal normal parts, and all their lengths are odd. Hence, for every even $n$ there are equally many partitions of $G_n(k)$ into two odd parts and into two even parts, the last of which is nonempty. This immediately yields $(***)$.

A remark on generalization. In the more general case of $d$-bonacci numbers, the desired relation on $V_r$ is $$ \sum_{\zeta^n=1}\frac{1-V_r(\zeta x)}{V_r(\zeta x)}=0. $$ The analysis from part 2 may be done similarly (the heads are still all-ones or all-zeroes, the tails are strings containing no $d$ consecutive ones and no $d$ consecutive zeroes), so the function can still be written in terms of $N_r(x)$. However, the obtained equation for $N_r$ looks different...

Answer 2

Here is some more data:

\begin{array}{l} V_8(x)=\frac{1-40 x^2-969 x^4-428 x^6-4 x^8}{1-2 x-40 x^2-174 x^3-969 x^4-2 x^5-428 x^6+174 x^7-4 x^8+4 x^9} \\ V_9(x)=\frac{1-62 x^2-2819 x^4-900 x^6}{1-2 x-62 x^2-386 x^3-2819 x^4-62 x^5-900 x^6+450 x^7} \\ V_{10}(x)= \frac{1-96 x^2-7945 x^4-1852 x^6-4 x^8}{1-2 x-96 x^2-830 x^3-7945 x^4-2 x^5-1852 x^6+830 x^7-4 x^8+4 x^9} \\ V_{11}(x)=\frac{1-153 x^2-21249 x^4+86213 x^6+18348 x^8}{1-2 x-153 x^2-1740 x^3-21249 x^4+9432 x^5+86213 x^6+1484 x^7+18348 x^8-9174 x^9} \\ \end{array}

Note that for $V_{11}$, the leading coefficient in the denominator is negative. Is it possible to predict some adjustment factor to multiply in the numerator and denominator (say $1-c x^2$) for some $c$ to make the degrees be predictable?

Perhaps so that the coefficient of $x^2$ in the denominator matches https://oeis.org/A006999 or https://oeis.org/A289010