fibonacci identity using generating function - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T01:26:18Z http://mathoverflow.net/feeds/question/11972 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/11972/fibonacci-identity-using-generating-function fibonacci identity using generating function serargus 2010-01-16T07:51:20Z 2010-01-16T08:01:22Z <p>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?</p> <p>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?</p> http://mathoverflow.net/questions/11972/fibonacci-identity-using-generating-function/11973#11973 Answer by Qiaochu Yuan for fibonacci identity using generating function Qiaochu Yuan 2010-01-16T08:01:22Z 2010-01-16T08:01:22Z <p>Apply the technique described <a href="http://qchu.wordpress.com/2009/10/07/extracting-the-diagonal/" rel="nofollow">in this blog post</a> 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.</p>