Learn Math The Easiest

« Encoding Matrices and Linear Codes

Parity Check Matrix and Dual Codes »

A Telescoping Solution To MMM #35

July 4th, 2009

Here is a problem from wildaboutmath.com Math Monday Madness #35

Simplify $F(0)F(1)+F(1)F(2)+\cdots +F(n-1)F(n)+F(n)F(n+1)$ where $F(0)=F(1)=1$ and $F(n)=F(n-1)+F(n-2)$ for $n\geq 2$ .

Solution

If $n$ is even, $n=2m$ the above expression is equal to

$\begin{aligned}&1+\sum_{k=0}^{m-1}F(2k+1)F(2k+2)+F(2k+2)F(2k+3)\\&=1+\sum_{k=0}^{m-1}F(2k+2)\left(F(2k+3)+F(2k+1)\right)\\&=1+\sum_{k=0}^{m-1}\left(F(2k+3)-F(2k+1)\right)\left(F(2k+3)+F(2k+1)\right)\\&=1+\sum_{k=0}^{m-1}F(2k+3)^2-F(2k+1)^2\\&=1+F(2m+1)^2-F(1)^2\\&=F(n+1)^2\end{aligned}$

If $n$ is odd, $n=2m+1$ and the expression equals

$\begin{aligned}&\sum_{k=0}^m F(2k)F(2k+1)+F(2k+1)F(2k+2)\\&=\sum_{k=0}^m F(2k+1)\left(F(2k+2)+F(2k)\right)\\&=\sum_{k=0}^m \left(F(2k+2)-F(2k)\right)\left(F(2k+2)+F(2k)\right)\\&=\sum_{k=0}^m F(2k+2)^2-F(2k)^2\\&=F(2m+2)^2-F(0)^2\\&=F(n+1)^2-1\end{aligned}$