# The Fibonacci sum $\sum_{n=0}^\infty \frac{1}{F_{2^n}}$ generalized

The evaluation,

$$\sum_{n=0}^\infty \frac{1}{F_{2^n}}=\frac{7-\sqrt{5}}{2}=\left(\frac{1-\sqrt{5}}{2}\right)^3+\left(\frac{1+\sqrt{5}}{2}\right)^2$$

was recently asked in a post by Chris here.

I like generalizations, and it turns out this is not a unique feature of the Fibonacci numbers. If we use the Pell numbers $P_m = 1,2,5,12,29,70,\dots$ then the sum is also an algebraic number of deg 2. In general, it seems for any positive rational b, then,

$$\sum_{n=0}^\infty \frac{1}{\frac{1}{\sqrt{b^2+4}}\left( \left(\frac{b+\sqrt{b^2+4}}{2}\right)^{2^n}-\left(\frac{b-\sqrt{b^2+4}}{2}\right)^{2^n}\right)}=1+\frac{2}{b}+\frac{b-\sqrt{b^2+4}}{2}$$

where Fibonacci numbers are just the case b = 1, the Pell numbers b = 2, and so on. (For negative rational b, then one just uses the positive case of $\pm\sqrt{b^2+4}$.)

Anyone knows how to prove/disprove the conjectured evaluation?

-
The induction approach mentioned in the linked post ought to work; the key point is that you can use the index-doubling formula of the associated sequence - which comes from the matrix representation of the sequence's shift operator - to explicitly express the partial sums. –  Steven Stadnicki Jun 13 '12 at 15:40
(also, is there a typo in your second formula? You use the expressions $\frac{1}{2}(b^2\pm\sqrt{b^2+4})$ where I assume you mean $\frac{1}{2}(b\pm\sqrt{b^2+4})$...) –  Steven Stadnicki Jun 13 '12 at 15:42
Oops,you are right. I've corrected the typo. –  Tito Piezas III Jun 13 '12 at 15:45

Your conjecture is indeed right. Before proving your conjecture, let us obtain an intermediate result first. Let us prove the following claim first.

CLAIM:

If we have a sequence given by the recurrence, $$a_{n+2} = ba_{n+1} + a_n,$$ with $a_0 =0$ and $a_1 = 1$, we then have $$\boxed{\color{blue}{\displaystyle \sum_{k=0}^{N} \dfrac1{a_{2^k}} = 1 + \dfrac2b - \dfrac{a_{2^N-1}}{a_{2^N}}}}$$

Proof: Let us write out a few terms of this sequence, we get $$a_0 = 0, a_1 = 1, a_2 = b, a_3 = b^2 + 1, a_4 = b^3 + 2b, \cdots$$ The proof is by induction on $N$. For $N=1$, we have the left hand side to be $$\dfrac1{a_1} + \dfrac1{a_2} = 1 + \dfrac1b$$ while the right hand side is $$1 + \dfrac2b - \dfrac{a_1}{a_2} = 1 + \dfrac2b - \dfrac1{b} = 1 + \dfrac1b$$ For $N=2$, we have the left hand side to be $$\dfrac1{a_1} + \dfrac1{a_2} + \dfrac1{a_4} = 1 + \dfrac1b + \dfrac1{b^3 + 2b}$$ while the right hand side is $$1 + \dfrac2b - \dfrac{a_3}{a_4} = 1 + \dfrac2b - \dfrac{b^2+1}{b^3+2b} = 1 + \dfrac1b + \dfrac1b - \dfrac{b^2+1}{b^3+2b} = 1 + \dfrac1b + \dfrac1{b^3+2b}$$ Hence, it holds for $N=1$ and $N=2$. Now lets go ahead with induction now. Assume the result is true for $N=m$ i.e. we have $$\sum_{k=0}^{m} \dfrac1{a_{2^k}} = 1 + \dfrac2b - \dfrac{a_{2^m-1}}{a_{2^m}}$$ Now $$\sum_{k=0}^{m+1} \dfrac1{a_{2^k}} = 1 + \dfrac2b - \dfrac{a_{2^m-1}}{a_{2^m}} + \dfrac1{a_{2^{m+1}}}$$ Hence, we want to show that $$- \dfrac{a_{2^m-1}}{a_{2^m}} + \dfrac1{a_{2^{m+1}}} = -\dfrac{a_{2^{m+1}-1}}{a_{2^{m+1}}}$$ i.e. $$\dfrac1{a_{2^{m+1}}} + \dfrac{a_{2^{m+1}-1}}{a_{2^{m+1}}} = \dfrac{a_{2^m-1}}{a_{2^m}}$$ i.e. $$a_{2^m}(1+a_{2^{m+1}-1}) = a_{2^m-1} a_{2^{m+1}} \,\,\,\, (\star)$$ which can be verified using the recurrence. In fact $(\dagger)$, a slightly more general version of $(\star)$, which is easier to check is true. $$a_{2k}(1+a_{4k-1}) = a_{2k-1} a_{4k} \,\,\,\, (\dagger)$$ i.e. $$a_{2k-1} a_{4k} - a_{2k} a_{4k-1} = a_{2k} \,\,\,\, (\dagger)$$ Hence, we get that $$\boxed{\color{red}{\displaystyle \sum_{k=0}^{N} \dfrac1{a_{2^k}} = 1 + \dfrac2b - \dfrac{a_{2^N-1}}{a_{2^N}}}}$$

Now letting $N \to \infty$, we see that your conjecture is indeed right. This is so since from the recurrence we get that $$\dfrac{a_{n+2}}{a_{n+1}} = b + \dfrac{a_n}{a_{n+1}}$$ If we have $\displaystyle \lim_{n \to \infty} \dfrac{a_n}{a_{n+1}} = L$, then we get that $$\dfrac1L = b + L$$ and since $L>0$, we have $L = \dfrac{\sqrt{b^2+4}-b}2$. Hence, $$\boxed{\color{red}{\displaystyle \sum_{k=0}^{\infty} \dfrac1{a_{2^k}} = \lim_{N \to \infty} \displaystyle \sum_{k=0}^{N} \dfrac1{a_{2^k}} = 1 + \dfrac2b - \lim_{N \to \infty} \dfrac{a_{2^N-1}}{a_{2^N}} = 1 + \dfrac2b - L = 1 + \dfrac2b + \dfrac{b}2 -\dfrac{\sqrt{b^2+4}}2}}$$

EDIT

After some googling, I found out that a similar result is true for a more general class of recurrences of the form $$a_{n+1} = P a_n + Q a_{n-1}$$ See this article for more details.

Also, try googling Millin series for more details.

-
+1 for going through the slog of the math and especially for the information about further generalizations - great stuff! –  Steven Stadnicki Jan 21 '13 at 18:02
@StevenStadnicki Yes. The trick was to get the right claim for finite $N$ i.e. to get $$\color{blue}{\displaystyle \sum_{k=0}^{N} \dfrac1{a_{2^k}} = 1 + \dfrac2b - \dfrac{a_{2^N-1}}{a_{2^N}}}.$$ Once we had it, the rest is just plain simple induction and then to let $N \to \infty$. –  user17762 Jan 21 '13 at 18:05
Thanks, Marvis! (I am on vacation, so didn't see your answer till now.) –  Tito Piezas III Jan 25 '13 at 3:10
And also for the links. They were most helpful. –  Tito Piezas III Jan 25 '13 at 3:39