I have to simplify the expression $\sum_{n=0}^\infty \sum_{k=0}^n \frac{F_{2k}F_{n-k}}{10^n}$. I only noticed that $\sum_{n=0}^\infty \sum_{k=0}^n \frac{F_{2k}F_{n-k}}{10^n} = \sum_{n=0}^\infty \frac{1}{10^n} \sum_{k=0}^n F_{2k}F_{n-k}$. What to do next?
Asked
Active
Viewed 104 times
2 Answers
2
The generating function of the Fibonacci numbers is well-known: $$ \frac{x}{1-x-x^2} = \sum_{n=0}^\infty F_n x^n. $$ We also want to isolate only the even Fibonacci numbers: $$ \frac{x}{1-x-x^2} + \frac{-x}{1+x-x^2} = \sum_{n=0}^\infty F_n (x^n + (-x)^n) = \sum_{n=0}^\infty 2F_{2n} x^{2n}. $$ Since $$ \frac{x}{1-x-x^2} + \frac{-x}{1+x-x^2} = \frac{x(1+x-x^2) -x(1-x-x^2)}{(1-x-x^2)(1+x-x^2)} = \frac{2x^2}{(1-x^2)^2-x^2}, $$ we can conclude that $$ \frac{x}{1-3x+x^2} = \sum_{n=0}^\infty F_{2n} x^n. $$ It follows that $$ \frac{x}{1-x-x^2} \frac{x}{1-3x+x^2} = \sum_{n=0}^\infty x^n \sum_{k=0}^n F_{2k} F_{n-k}. $$ In particular, your expression equals $100/6319$.
Yuval Filmus
- 57,157
0
There's nothing special about $10$ here: you might as well replace it by $1/x$.
Suggestion: interchange the order of the summations. Do you know the generating function of the Fibonacci numbers?
Robert Israel
- 448,999