2
$\begingroup$

There are many nice ways of showing that $f_0^2+f_1^2+\cdots+f_n^2=f_{n+1}f_n$. I was wondering if there is a way of showing this using the generating function $F(x)=\frac{1}{1-x-x^2}=\sum_{i\geq0}f_ix^i$. In other words, is there any operation (perhaps the Hadamard product) that can be applied to $F(x)$ that would yield the identity above?

What about other identities that involve sums and squares, like $f_1f_2+\cdots +f_nf_{n+1}=f_{n+1}^2$ for $n$ odd?

$\endgroup$

2 Answers 2

7
$\begingroup$

Apply the technique described in this blog post to $F(x) F(y)$, then to $x F(x) F(y)$. The key observation here is that one can compute Hadamard products of rational functions using the residue theorem.

$\endgroup$
7
$\begingroup$

Here are the details on proving these identities using Hadamard products of generating functions. (You can find explanations of how to compute Hadamard products of rational functions here.)

I'll write $U(x)*V(x)$ for the Hadmard product of $U(x)$ and $V(x)$: $$\sum_{n=0}^\infty u_n x^n *\sum_{n=0}^\infty v_n x^n =\sum_{n=0}^\infty u_n v_n x^n.$$

Let $$F=\sum_{n=0}^\infty f_n x^n =\frac{1}{1-x-x^2}$$ and let $$F_1 = \sum_{n=0}^\infty f_{n+1}x^n = (F-1)/x = \frac{1-x}{1-x-x^2}.$$ Then we have $$ \sum_{n=0}^\infty f_{n}^2x^n=F*F=\frac{1-x}{1-2x-2x^2+x^3} $$ and $$ \sum_{n=0}^\infty f_{n}f_{n+1}x^n = F*F_1 = \frac{1}{1-2x-2x^2+x^3}. $$ Thus $(F*F)/(1-x) =F*F_1$. This proves the first identity $f_0^2 + \cdots + f_n^2 = f_{n+1}f_n$.

The second identity is stated incorrectly. It should be $$f_0f_1 + f_1f_2 +\cdots +f_n f_{n+1}= \begin{cases} f_{n+1}^2,&\text{if $n$ is even}\\ f_{n+1}^2 -1,&\text{if $n$ is odd}. \end{cases} $$ The generating function for the left side is $$\frac{F*F_1}{1-x}=\frac{1}{(1-x)(1-2x-2x^2+x^3)}.$$ We have $$\sum_{n=0}^\infty f_{n+1}^2 x^n = F_1*F_1= \frac{1+2x-x^2}{1-2x-2x^2+x^3}$$ and we find that $$\frac{F*F_1}{1-x} -F_1*F_1 = -\frac{x}{1-x^2},$$ which proves the corrected second identity.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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