Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
  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?

share|improve this question
    
for the second part $\sum _{k=0}^{\infty }\dfrac {F^{k}} {p^{k}}=\dfrac {p} {p^2 - p-1}$ for $p\geq 0$ source en.wikipedia.org/wiki/Fibonacci_number#Power_series –  Hardy Aug 7 '12 at 10:41
    
See this for the second part. –  J. M. Aug 7 '12 at 11:14

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
    
I don't know which identity to use to simplify $\sum_{k=0}^n F_{2k}F_{n-k}$ –  ray Aug 7 '12 at 15:01
    
@ray: You could try to prove $\sum_{k=0}^n F_{2k}F_{n-k} = \frac{F_{2n+1}-F_{n+2}}{2}$ by induction –  Henry Aug 7 '12 at 15:57
    
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. –  ray Aug 7 '12 at 16:05
    
@ray: work out the first few terms, look it up on OEIS and find A056014 which says "Convolution of Fibonacci numbers F(n) with F(2n)" –  Henry Aug 7 '12 at 18:17
    
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. –  ray Aug 7 '12 at 19:15

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}.$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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