Find the sum of an infinite series of Fibonacci numbers divided by doubling numbers.

Question

How would I find the sum of an infinite number of fractions, where there are Fibonacci numbers as the numerators (increasing by one term each time) and numbers (starting at one) which double each time as the denominators?

I'm assuming this has something to do with limits.

Answer 1

Using Moivre-Binet $$ F_n = \frac{\phi^n - \psi^n}{\phi - \psi} $$ with $\phi$ and $\psi$ being the positive and negative root of the golden ratio equation $x^2 - x - 1 = 0$, we get

\begin{align} \sum_{n=0}^\infty \frac{F_n}{2^n} &= \frac{1}{\phi - \psi} \sum_{n=0}^\infty \frac{\phi^n-\psi^n}{2^n} \\ &= \frac{1}{\phi - \psi} \sum_{n=0}^\infty \left(\frac{\phi}{2}\right)^n - \frac{1}{\phi - \psi} \sum_{n=0}^\infty \left(\frac{\psi}{2}\right)^n \\ &= \frac{1}{\phi - \psi} \frac{1}{1 - \frac{\phi}{2} } - \frac{1}{\phi - \psi} \frac{1}{1 - \frac{\psi}{2} } \\ &= \frac{2}{\phi - \psi} \left( \frac{1}{2 - \phi} - \frac{1}{2 - \psi} \right) \\ &= \frac{2}{\phi - \psi} \left( \frac{(2-\psi) - (2-\phi)}{(2 - \phi)(2-\psi)} \right) \\ &= \frac{2}{\phi - \psi} \left( \frac{\phi - \psi}{4 - 2 \phi - 2 \psi + \phi \psi} \right) \\ &= \frac{2}{4 - 2 (\phi + \psi) + \phi \psi} \\ &= \frac{2}{4 - 2 + (-1)} \\ &= 2 \end{align} Note: The geometric series converge because $\lvert \phi/2 \rvert < 1$ and $\lvert \psi/2 \rvert < 1$.

Appendix: $$ x^2 - x - 1 = 0 \iff x = \frac{1 \pm \sqrt{5}}{2} $$ Thus $$ \phi + \psi = \frac{1 + \sqrt{5}}{2} + \frac{1 - \sqrt{5}}{2} = 1 $$ and $$ \phi \psi = \frac{1 + \sqrt{5}}{2} \frac{1 - \sqrt{5}}{2} = \frac{1 - 5}{4} = -1 $$

Answer 2

I assume the sum you want to compute is $$ \sum_{n=0}^\infty\frac{F_n}{2^n}$$ where $F_n$ is the $n$'th Fibonacci number ($F_0=F_1=1$ and $F_n = F_{n-1}+F_{n-2}$ for $n\ge 2$). One simple way of computing this is to use the closed form of $F_n$, namely $$F_n=\frac{1}{\sqrt{5}}\left(\Biggl(\frac{1+\sqrt{5}}{2}\Biggr)^{n}-\Biggl(\frac{1-\sqrt{5}}{2}\Biggr)^{n}\right).$$ Inserting this into the sum, and using that $\sum_{n=0}^\infty a^n = \frac{1}{1-a}$ for $|a|<1$, you get \begin{align} \sum_{n=0}^\infty\frac{F_n}{2^n}&= \frac{1}{\sqrt{5}}\sum_{n=0}^\infty\left(\Biggl(\frac{1+\sqrt{5}}{4}\Biggr)^{n}-\Biggl(\frac{1-\sqrt{5}}{4}\Biggr)^{n}\right)\\ &=\frac{1}{\sqrt{5}}\frac{1}{1-(1+\sqrt{5})/4}-\frac{1}{\sqrt{5}}\frac{1}{1-(1-\sqrt{5})/4)}\\ &= 2 \end{align}

Answer 3

Here's a reasonably efficient low-tech approach (i.e., not using Binet's formula or generating functions).

Prove by induction that $$ \sum_{k=0}^n \frac{F_k}{2^k} = 2 - \frac{F_{n+3}}{2^n} \tag{1} $$ and that $$ nF_n \le 2^n \tag{2} $$ (For (2) you might find it convenient to assume $n\ge 6$.) From (2) it follows that $\frac{F_{n+3}}{2^n} \le \frac8{n+3} \to 0$, so the partial sums in (1) converge.

Answer 4

This is a standard infinite sequence problem. It starts with just this: $$\sum_{n=0}^\infty \frac{F_n}{2^n}=$$ $$\frac11+\frac12+\frac24+\frac38+\frac5{16}+\frac8{32}+...$$

---

let S equal the sequence of fractions:

$S=\frac11+\frac12+\frac24+\frac38+\frac5{16}+\frac8{32}+...$

Divide by 2 and get:

$\frac{S}2=\frac12+\frac14+\frac28+\frac3{16}+\frac5{32}+...$

Subtract the first from the second to get:

$S-\frac{S}2=1+\frac02+\frac14+\frac18+\frac2{16}+\frac3{32}+...$

Simplify:

$\frac{S}2=1+\frac14+\frac18+\frac2{16}+\frac3{32}+...$

Multiply both sides by two:

$S=2+\frac12+\frac14+\frac2{8}+\frac3{16}+...$

$2S=4+\frac11+\frac12+\frac24+\frac3{8}+...$

Recognize S from above:

$2S=4+S$

Subtract S from both sides:

$S=4$