# partial Fibonacci summation

Let $F_{n}$ be the n-th Fibonacci number. How to calculate the summation like following:

$\sum_{n \geq 0} F_{3n} \cdot 2^{-3n}$

-
Do you know Binet's formula? It lets you make this sum the same as a geometric series. – Thomas Andrews Mar 1 '14 at 4:16

Here's an approach via generating functions. As the Fibonacci recurrence is defined by $F_{n+2} = F_{n+1} + F_n$, we have $$\sum_{n \ge 0} F_{n+2}z^{n+2} = \sum_{n \ge 0} F_{n+1}z^{n+1}z + \sum_{n \ge 0}F_nz^nz^2$$ which with the generating function $G(z) = \sum_{n\ge0} F_n z^n$ gives $$G(z) - F_0 - F_1z = zG(z) - zF_0 + z^2G(z)$$ and therefore (using $F_0 = 0$ and $F_1 = 1$), $$G(z) - z = zG(z) + z^2G(z) \implies G(z) = \frac{z}{1 - z - z^2}.$$

This much is well-known. Now let $\omega$ be a third root of unity, so that $\omega^3 = 1$. Then $$G(z) + G(z\omega) + G(z\omega^2) = \sum_{n\ge0} F_nz^n(1 + \omega^n + \omega^{2n}) = \sum_{n\ge0} 3F_{3n}z^{3n},$$ as we have $$1 + \omega^n + \omega^{2n} = \begin{cases} 3 \text{ if 3 divides n}\\0 \text{ otherwise.}\end{cases}$$

This means that the number $\sum_{n\ge0} F_{3n}2^{-3n}$ we want is $$\frac{G(z) + G(z\omega) + G(z\omega^2)}{3}$$ with $z = \frac12$. The sum turns out to be $$\frac13\left(\frac{1/2}{1-1/2-(1/2)^2} + \frac{\omega(1/2)}{1-\omega(1/2)-\omega^2(1/2)^2} + \frac{\omega^2(1/2)}{1-\omega^2(1/2)-\omega(1/2)^2}\right)$$ $$=\frac13\left(2 - \frac{14}{31}\right) = \frac{16}{31}.$$

-
(Convergence issues are fine because $\frac12$ is within the radius of convergence, which is $1/|\phi|$.) – ShreevatsaR Mar 2 '14 at 12:49
Thank your for the answer! A minor question: how do you know $1 + \omega^n + \omega^{2n} = 0 \text{ when 3 can't divide n.}$ – cinvro Mar 2 '14 at 19:59
@cinvro: Well, for $n=1$, it is true because $\omega$ is a solution to $0=x^3-1=(x-1)(x^2+x+1)$, so (as we're not taking $\omega=1$), it satisfies $x^2+x+1=0$. For larger $n$ not divisible by $3$, $\omega^n$ and $\omega^{2n}$ are simply $\omega$ and $\omega^2$, possibly swapped. (Note that $\omega^{3k+1}=(\omega^3)^k\omega =1^k\omega=\omega$, and similarly $\omega^{3k+2}=\omega^2$.)Another way of seeing this: $\omega^3=1$ so $\omega^{3n}=1^n=1$, which means that $0 = \omega^{3n}-1 = (\omega^n - 1)(1 + \omega^n + \omega^{2n})$, and the first term is nonzero when $n$ is not divisible by $3$. – ShreevatsaR Mar 2 '14 at 20:07

As suggested, the simplest would consist in a use of Binet formula for Fibonacci number. It write $$F_n=\frac{\varphi ^n-\psi ^n}{\sqrt{5}}$$ with $\varphi=\frac{1}{2} \left(1+\sqrt{5}\right)$ and $\psi=\frac{1}{2} \left(1-\sqrt{5}\right)$. So, if we consider each term of the sum, we can rewrite it as $$F_{3n}2^{-3n}=\frac{\Phi ^n-\Psi ^n}{\sqrt{5}}$$ noting $$\Phi=\frac{1}{8} \left(1+\sqrt{5}\right)^3$$ and $$\Psi=\frac{1}{8} \left(1-\sqrt{5}\right)^3$$ Now, we consider the partial sum from $n=1$ to $n=m$ and apply the rules of geometric progressions. So we obtain $$\sum _{n=1}^m F_{3n}2^{-3n}=\frac{\frac{\Phi \left(\Phi ^m-1\right)}{\Phi -1}-\frac{\Psi \left(\Psi ^m-1\right)}{\Psi -1}}{\sqrt{5}}$$

-
I am sorry, I am not looking for that partial summation but taking n from 0 to infinity – cinvro Mar 1 '14 at 6:47
You asked for partial summation in the title of your post. Please edit. – Claude Leibovici Mar 1 '14 at 6:57
sorry for the mistake, I edited the question. Could you please modify your answer a little bit to fit the question again? Thank you! – cinvro Mar 2 '14 at 5:57

$F_0 = 0$, $F_1 = 1$, and $F_{n+2} = F_n + F_{n+1}$.

$F_{n+3} = F_n + 2F_{n+1}$

$F_{n+6} = 5F_n + 8F_{n+1} = F_n + 4F_{n+3}$

Let G be a series where $G_0 = 0$, $G_1 = 2$, and $G_{n+2} = G_n + 4G_{n+1}$. In other words, $G_i = F_{3i}$. Its generating function is $g(x) = \dfrac{2x}{1 - 4x - x^2}$.

$\sum_{n \ge 0}F_{3n}2^{-3n} = \sum_{n \ge 0} G_n{\left(\dfrac18\right)}^{n} = g(\dfrac18) = \dfrac{16}{31}$

-