How can I proof the binomial formula by using the generating function of $q_m$?

Question

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.

Answer 1

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.

Conclusion:

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).