7
$\begingroup$
  1. Find closed form formula for sum: $\displaystyle\sum_{n=0}^{+\infty}\sum_{k=0}^{n} \frac{F_{2k}F_{n-k}}{10^n}$

  2. Find closed form formula for sum: $\displaystyle\sum_{k=0}^{n}\frac{F_k}{2^k}$ and its limit with $n\to +\infty$.

First association with both problems: generating functions and convolution. But I have been thinking about solution for over a week and still can't manage. Can you help me?

  • 0
    for the second part $\sum _{k=0}^{\infty }\dfrac {F^{k}} {p^{k}}=\dfrac {p} {p^2 - p-1}$ for $p\geq 0$ source http://en.wikipedia.org/wiki/Fibonacci_number#Power_series2012-08-07
  • 0
    See [this](http://math.stackexchange.com/questions/88529) for the second part.2012-08-07

2 Answers 2

1

For (2) you have $F_k = \dfrac{\varphi^k}{\sqrt 5}-\dfrac{\psi^k}{\sqrt 5}$ where $\varphi = \frac{1 + \sqrt{5}}{2} $ and $\psi = \frac{1 - \sqrt{5}}{2}$ so the problem becomes the difference between two geometric series.

For (1) I think you can turn this into something like $\displaystyle \sum_{n=0}^{\infty} \frac{F_{2n+1}-F_{n+2}}{2\times 10^n}$ and again make it into a sum of geometric series.

There are probably other ways.

  • 0
    I don't know which identity to use to simplify $\sum_{k=0}^n F_{2k}F_{n-k}$2012-08-07
  • 0
    @ray: You could try to prove $\sum_{k=0}^n F_{2k}F_{n-k} = \frac{F_{2n+1}-F_{n+2}}{2}$ by induction2012-08-07
  • 0
    I know, but it isn't well known identity, I think. At least I couldn't find it on wiki. I'm wondering how it can be deduced.2012-08-07
  • 0
    @ray: work out the first few terms, look it up on OEIS and find [A056014](http://oeis.org/A056014) which says "Convolution of Fibonacci numbers F(n) with F(2n)"2012-08-07
  • 0
    thank you. Unfortunately OEIS will not help me during the exam or something like that. But I came up with slightly different solution and I think as good as yours. Indeed it is a convolution of F(2n) with F(n) so all we need is to find generating functions for both sequences which is easy. Then multiply them and the answer is its value for $z=1/10$. I like finding more than one solution. Thanks once again.2012-08-07
2

The first one can be solved using the fact that the generating function of the Fibonacci numbers is $$\frac{z}{1-z-z^2}.$$ Introduce the function $$f(z) = \sum_{n\ge 0} z^n \sum_{k=0}^n \frac{F_{2k} F_{n-k}}{10^n}$$ so that we are interested in $f(1).$

Re-write $f(z)$ as follows: $$f(z) = \sum_{k\ge 0} F_{2k} \sum_{n\ge k} \frac{z^n}{10^n} F_{n-k} = \sum_{k\ge 0} F_{2k} \frac{z^k}{10^k} \sum_{n\ge 0} \frac{z^n}{10^n} F_n.$$

Now we have $$ \sum_{k\ge 0} F_{2k} z^{2k} = \frac{1}{2} \frac{z}{1-z-z^2} - \frac{1}{2} \frac{z}{1+z-z^2}$$ and therefore $f(1)$ is $$\left(\frac{1}{2} \frac{1/\sqrt{10}}{1-1/\sqrt{10}-1/10} - \frac{1}{2} \frac{1/\sqrt{10}}{1+1/\sqrt{10}-1/10}\right) \times \frac{1/10}{1-1/10-1/100}$$ which simplifies to $$\frac{1}{2\sqrt{10}} \frac{2/\sqrt{10}}{81/100-1/10} \times \frac{10}{89} = \frac{1}{10} \times \frac{1}{71/100} \times \frac{10}{89} = \frac{100}{89\times 71}.$$