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