2
$\begingroup$

How to find the sum $\sum_{i = 0}^{\infty}\frac{F_i}{7^i}$?

$F_i$ - $i$-th Fibonacci number

My solution:

I think that that's right to use generating functions.

For Fibonacci number the generating function looks like $\mathcal{F}(z) = \frac{z}{-z^2 - z + 1} $ For the sequence $7^n$ the generating function is $\mathcal{A}(z) = \frac{1}{1 - 7 z}$. But I can't guess now how to use my results to find given sum.

$\endgroup$
6
  • 1
    $\begingroup$ How is the generating function of the Fibonacci sequence defined, already? $\endgroup$ – Did Nov 2 '15 at 9:02
  • $\begingroup$ @Did $\mathcal{F}(z) = \sum_{i = 0}^{\infty} F_i z^i $ $\endgroup$ – J.Exactor Nov 2 '15 at 9:05
  • 4
    $\begingroup$ Can't you plug in some suitable value of $z$ so that it would look kinda familiar? $\endgroup$ – Ivan Neretin Nov 2 '15 at 9:12
  • $\begingroup$ The most natural way of solving this would be by using Binet's formula. $\endgroup$ – Lucian Nov 2 '15 at 9:18
  • 2
    $\begingroup$ So you know $\mathcal F(z)$ for every $z$ and you ask for $\mathcal F(1/7)$? $\endgroup$ – Did Nov 2 '15 at 9:23
3
$\begingroup$

Without generating function:

We establish the recurrence

$$\frac{F_i}{7^i}=\frac{F_{i-1}+F_{i-2}}{7^i}=\frac17\frac{F_{i-1}}{7^{i-1}}+\frac1{49}\frac{F_{i-2}}{7^{i-2}}.$$

Then we extend it to the summation

$$\sum_{i=2}^\infty \frac{F_i}{7^i}=\frac17\sum_{i=2}^\infty \frac{F_{i-1}}{7^{i-1}}+\frac1{49}\sum_{i=2}^\infty \frac{F_{i-2}}{7^{i-2}},$$

giving $$S-\frac{F_1}{7^1}-\frac{F_0}{7^0}=\frac17(S-\frac{F_0}{7^0})+\frac1{49}S,$$ so that

$$S(1-\frac17-\frac1{49})=\frac17,\\S=\frac7{41}.$$

$\endgroup$
1
  • $\begingroup$ This is indeed a generating function approach that doesn't tell its name (replace $1/7$ by $z$), but from scratch. $\endgroup$ – Yves Daoust Nov 2 '15 at 10:10
6
$\begingroup$

You know $\frac{z}{-z^2 - z + 1} = \mathcal{F}(z) = \sum_{i = 0}^{\infty} F_i z^i$ for any $z$. In particular for $z=1/7$: $$ \sum_{i = 0}^{\infty}\frac{F_i}{7^i} = \mathcal{F}(1/7) = \frac{1/7}{-(1/7)^2 - 1/7 + 1}. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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