Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

3 Answers 3

up vote 3 down vote accepted

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

share|improve this answer
    
(Convergence issues are fine because $\frac12$ is within the radius of convergence, which is $1/|\phi|$.) –  ShreevatsaR Mar 2 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 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 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}}$$

share|improve this answer
    
I am sorry, I am not looking for that partial summation but taking n from 0 to infinity –  cinvro Mar 1 at 6:47
    
You asked for partial summation in the title of your post. Please edit. –  Claude Leibovici Mar 1 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 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}$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.