partial Fibonacci summation

Question

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

Answer 1

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

Answer 2

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

Answer 3

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