The authors give the generating function of the generalized Fibonacci polynomial and they proof the Theorem 2.4 in (http://users.dimi.uniud.it/~giacomo.dellariccia/Glossary/Lucas/NalliHaukkanen2009.pdf) \begin{eqnarray} \sum_{n=0}^{\infty} F_{h,n}(x)t^n &=& \frac{t}{1-\left( h(x)t + t^2 \right)} = t \sum_{n=0}^{\infty} \left( h(x)t +t^2 \right)^n \nonumber \\ & = &t \sum_{n=0}^{\infty} \sum_{i=0}^{n} \binom{n}{i} \left( h(x)t \right)^{n-i} \left(t^2\right)^i \nonumber \\ & = & \sum_{n=0}^{\infty} \sum_{i=0}^{n} \binom{n}{i} h^{n-i}(x)t^{n+i+1}. \nonumber \end{eqnarray} Writing $n+i+1=m$, they obtain \begin{equation} \sum_{n=0}^{\infty} F_{h,n}(x)t^n = \sum_{m=0}^{\infty} \left[ \sum_{i=0}^{\lfloor \frac{m-1}{2} \rfloor} \binom{m-i-1}{i} h^{m-2i-1} \right] t^m. \nonumber \end{equation} Thus, they extract the binomial formula from the above equation and they get \begin{equation} F_{h,n}(x) = \sum_{i=0}^{\lfloor \frac{m-1}{2} \rfloor} \binom{m-i-1}{i} h^{m-2i-1}. \nonumber \end{equation} Now, we have a generating function \begin{equation} F(x) = \sum_{n=0}^{\infty} q_n x^n = \frac{x \left( 1+ax-x^2 \right)}{1- (ab+2)x^2 + x^4} \nonumber. \end{equation} The authors give the binomial formula with Theorem 2 in ( http://www.sciencedirect.com/science/article/pii/S0096300310012403 ) as \begin{equation} q_m = a^{\xi(m-1)} \sum_{m=0}^{\lfloor \frac{m-1}{2} \rfloor } \binom{m-k-1}{k} \left( ab \right)^{\lfloor \frac{m-1}{2} \rfloor -k} \nonumber \end{equation} How can I proof the binomial formula of $q_m$ by using the generating function $F(x)$ similar to first proof? The authors proved it by using induction method but I will not use induction while prooving it. Thank you.


A derivation similar to that of $F_{h,n}(x)$ does not directly lead to the wanted binomial expression for $q_m$ but instead to another one. In a second step equality of these binomial expressions will be shown.

First step:

We consider the generating function \begin{align*} F(x)&=\sum_{n=0}^\infty q_nx^n=\frac{x(1+ax-x^2)}{1-(ab+2)x^2+x^4}\\ &=x+ax^2+(ab+1)x^3+a(ab+2)x^4+(a^2b^2+3ab+1)x^5+\cdots\\ \end{align*} and want to show \begin{align*} q_m&=[x^m]F(x)\\ &=a^{\frac{1+(-1)^m}{2}}\sum_{k=0}^{\left\lfloor\frac{m-1}{2}\right\rfloor} \binom{m-k-1}{k}(ab)^{\left\lfloor\frac{m-1}{2}\right\rfloor-k}\tag{1} \end{align*}

We obtain \begin{align*} F(x)&=\sum_{n=0}^\infty q_nx^n=\frac{x(1+ax-x^2)}{1-(ab+2)x^2+x^4}\\ &=x(1+ax-x^2)\sum_{n=0}^\infty\left((ab+2)x^2-x^4\right)^n\\ &=x(1+ax-x^2)\sum_{n=0}^\infty\sum_{k=0}^n\binom{n}{k}((ab+2)x^2)^{n-k}(-x^4)^k\\ &=(1+ax-x^2)\sum_{n=0}^\infty\sum_{k=0}^n\binom{n}{k}(-1)^k(ab+2)^{n-k}x^{2n+2k+1}\tag{2}\\ \end{align*}

In order to obtain $q_m$, the coefficient of $x^m$ of $F(x)$, it is convenient to consider even and odd case separately. When considering in (2) the factor $(1+ax-x^2)$ we see that even powers of $x$ are given when taking the term $ax$, while odd powers are obtained when taking the other two terms $1-x^2$.

Even powers: $m=2m^{\prime}$

We obtain by considering even powers in (2) \begin{align*} [x^{2m^{\prime}}]F(x)&=a[x^{2m^{\prime}}]\sum_{n=0}^\infty\sum_{k=0}^n\binom{n}{k}(-1)^k(ab+2)^{n-k}x^{2n+2k+2}\\ &=a\sum_{k=0}^{\left\lfloor\frac{m^{\prime}-1}{2}\right\rfloor}\binom{m^{\prime}-k-1}{k}(-1)^k(ab+2)^{m^{\prime}-2k-1}\tag{3} \end{align*} Here we have $2m^\prime=2n+2k+2$ which implies $m^\prime=n+k+1$ and the upper bound of the sum is derived from the binomial coefficient which gives $k\leq m^{\prime}-k-1$, resp. $k\leq \frac{m^{\prime}-1}{2}$.

Odd powers: $m=2m^{\prime}+1$

We obtain by considering odd powers in (2) \begin{align*} [x^{2m^{\prime}+1}]F(x)&=[x^{2m^\prime+1}]\sum_{n=0}^\infty\sum_{k=0}^n\binom{n}{k}(-1)^k(ab+2)^{n-k}x^{2n+2k+1}\\ &\qquad-[x^{2m^\prime+1}]\sum_{n=0}^\infty\sum_{k=0}^n\binom{n}{k}(-1)^k(ab+2)^{n-k}x^{2n+2k+3}\\ &=\sum_{k=0}^{\left\lfloor\frac{m^{\prime}}{2}\right\rfloor}\binom{m^{\prime}-k}{k}(-1)^k(ab+2)^{m^{\prime}-2k}\\ &\qquad -\sum_{k=0}^{\left\lfloor\frac{m^{\prime}-1}{2}\right\rfloor}\binom{m^{\prime}-k-1}{k}(-1)^k(ab+2)^{m^{\prime}-2k-1}\tag{4} \end{align*} Here we have $2m^\prime+1=2n+2k+1$ in the first summand and $2m^\prime+1=2n+2k+3$ in the second sum and we calculate similarly as we did in the even case.


For even $m=2m^\prime$ we compare (1) with (3) and see the validity of the following binomial identity has to be shown \begin{align*} \sum_{k=0}^{m^\prime-1} \binom{2m^\prime-k-1}{k}(ab)^{m^\prime-k-1}= \sum_{k=0}^{\left\lfloor\frac{m^{\prime}-1}{2}\right\rfloor}\binom{m^{\prime}-k-1}{k}(-1)^k(ab+2)^{m^{\prime}-2k-1}\tag{5} \end{align*}

For odd $m=2m^\prime+1$ we compare (1) with (4) and see the validity of the following binomial identity has to be shown \begin{align*} \sum_{k=0}^{m^\prime} \binom{2m^\prime-k}{k}(ab)^{m^\prime-k}&= \sum_{k=0}^{\left\lfloor\frac{m^{\prime}}{2}\right\rfloor}\binom{m^{\prime}-k}{k}(-1)^k(ab+2)^{m^{\prime}-2k}\\ &\qquad -\sum_{k=0}^{\left\lfloor\frac{m^{\prime}-1}{2}\right\rfloor}\binom{m^{\prime}-k-1}{k}(-1)^k(ab+2)^{m^{\prime}-2k-1}\tag{6} \end{align*}

Second step:

We prove the validity of the binomial identity (6) by showing that the odd powers of the generating function $G(x)$ of the left-hand side correspond with the odd powers of $F(x)$.

We consider \begin{align*} G(x)&=\sum_{m^\prime=0}^\infty\sum_{k=0}^{m^\prime}\binom{2m^\prime-k}{k}(ab)^{m^\prime-k}x^{2m^\prime+1}\\ &=x\sum_{m^\prime=0}^\infty\sum_{k=0}^{m^\prime}\binom{2m^\prime-k}{k}(x\sqrt{ab})^{2m^\prime-2k}x^{2k}\tag{$2m^{\prime}-k=n$}\\ &=x\sum_{n=0}^\infty\sum_{k=0}^{n}\binom{n}{k}(x\sqrt{ab})^{n-k}(x^2)^k\\ &=x\sum_{n=0}^\infty\left(x\sqrt{ab}+x^2\right)^n\\ &=\frac{x}{1-x\sqrt{ab}-x^2} \end{align*}

Since \begin{align*} \frac{G(x)+G(-x)}{2}&=\frac{1}{2}\left(\frac{x}{1-x\sqrt{ab}-x^2}+\frac{x}{1+x\sqrt{ab}-x^2}\right)\\ &=\frac{x(1-x^2)}{1-(ab+2)x^2-x^4}\\ &=x+(ab+1)x^3+(a^2b^2+3ab+1)x^5+\cdots\\ \end{align*} we obtain a generating function consisting of the odd powers of $F(x)$. Similarly we can show the validity of (5).

  • $\begingroup$ @drxy: Thanks a lot for accepting my answer and granting the bounty. $\endgroup$ – Markus Scheuer Dec 30 '17 at 7:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.