# How to find closed form of summation of Fibonacci Sequence?

I created two formulas to prove a binary theory involving the Fibonacci sequence.

(1) $\sum_{i=0}^n F_{2i+1}$

Equation (1) is the sum of all Fibonacci numbers up to $F_n$ where every $i$ in $F_i$ is an odd number.

I had come up with a closed form where (1) = $F_{n+1} -1$

Is this right? If so, how do I prove it?

• Hi! I think that your notation is wrong: what you're saying with those formulas is to sum all fibonacci numbers, alternating signs. I think you mean something like: $$(1)\qquad\sum_{i=0}^nF_{2i+1}$$ $$(2)\qquad\sum_{i=1}^nF_{2i}$$ If these formulae are correct, please edit your question. – cjferes Sep 25 '14 at 18:23
• Hey! You are right, I will edit. – Kris Sep 25 '14 at 18:32
• The question is still not correctly stated. The correct sum is $F_{2n+2}$. – rogerl Sep 25 '14 at 18:39
• And, computation of this and many other Fibonacci identities may be found here. – rogerl Sep 25 '14 at 18:41

This proof uses only the definition.

\begin{align*} F_{2n + 2} &= F_{2n + 1} + F_{2n} \\ &= F_{2n + 1} + F_{2n - 1} + F_{2(n-1)} \\ &= F_{2n + 1} + F_{2(n-1) + 1} + F_{2(n-2) + 1} + F_{2(n-2)} \\ &= \cdots \\ &= F_{2(n-k)} + \sum_{j = 0}^{k} F_{2(n-j) + 1} \end{align*} Setting $k = n$ in the last line, we obtain the desired formula $F_{2n + 2} = 1 + \sum_{j = 0}^n F_{2j + 1}$.

• +1 for giving a clean derivation that doesn't dip into the algebraic characterization at all. This has a nice combinatorial interpretation, too, using the characterization of the Fibonacci numbers as the number of sequences of $1$s and $2$s with total sum $n$: bucket the sequences according to where the first $1$ appears. – Steven Stadnicki Sep 25 '14 at 19:33

The Fibonacci numbers have the form $(\alpha - \beta) F_{n} = \alpha^{n} - \beta^{n}$, where $2 \alpha = 1 + \sqrt{5}$ and $2 \beta = 1 - \sqrt{5}$. Now \begin{align} \sum_{k=0}^{n} (-1)^{k} F_{k} &= \frac{1}{\alpha - \beta} \sum_{k=0}^{n} \left( (- \alpha)^{k} - (- \beta)^{k} \right) \\ &= \frac{1}{\alpha - \beta} \left( \frac{1 - (-\alpha)^{n+1}}{1+\alpha} - \frac{1 - (-\beta)^{n+1}}{1+ \beta} \right) \\ &= \frac{1}{\alpha - \beta} \left( (-1)^{n} (\alpha^{n-2} - \beta^{n-2}) - (\alpha^{2} - \beta^{2}) \right) \\ &= (-1)^{n} F_{n-2} - (\alpha + \beta) \\ &= (-1)^{n} F_{n-2} -1. \end{align} Since $F_{0} = 0$ the summation can also be seen as \begin{align} \sum_{k=1}^{n} (-1)^{k} F_{k} = (-1)^{n} F_{n-2} - 1. \end{align}

We have that $$F_n=\frac{1}{2}\left(\frac{1+\sqrt{5}}{2}\right)^{n-1} +\frac{1}{2}\left(\frac{1-\sqrt{5}}{2}\right)^{n-1}=\frac{1}{2}\big(\mu^{n-1}+\nu^{n-1}\big),$$ and hence $$s=\sum_{i=0}^n F_{2i+1}=\frac{1}{2}\sum_{j=0}^n\left(\mu^{2j}+\nu^{2j}\right)=\frac{1}{2} \left(\frac{\mu^{2n+2}-1}{\mu^2-1}+\frac{\nu^{2n+2}-1}{\nu^2-1}\right).$$ Next $$\mu^2-1=\frac{6+2\sqrt{5}}{4}-1=\frac{1+\sqrt{5}}{2}=\mu,\quad \nu^2-1=\cdots=\nu,$$ while $$\frac{1}{\mu}=\frac{2}{1+\sqrt{5}}=\frac{2\sqrt{5}-2}{4}=\nu.$$ Hence $$s=\frac{1}{2}\left(\mu^{2n+1}+\nu^{2n+1}-\frac{1}{\mu}-\frac{1}{\nu}\right)=F_{2n+2}-1.$$

Let's start with $$(1)\qquad \sum_{i=0}^NF_{2i+1}$$

As said in other answer, the Fibonnaci numbers have the form $$F_n=\frac{\alpha^n-\beta^n}{\alpha-\beta}$$

where $\alpha$ and $\beta$ are the roots of the polinomial $x^2-x-1=0$, so $\alpha^2-1=\alpha$ and $\beta^1-1=\beta$.

Then $$\begin{array}{rcl} \sum_{i=0}^NF_{2i+1}&=&\frac{1}{\alpha-\beta}\sum_{i=0}^N\big(\alpha^{2i+1}-\beta^{2i+1}\big)\\ &=&\frac{1}{\alpha-\beta}\Bigg(\alpha\sum_{i=0}^N\big(\alpha^2\big)^i-\beta\sum_{i=0}^N\big(\beta^2\big)^i\Bigg)\\ &=&\frac{1}{\alpha-\beta}\Bigg(\alpha\frac{\big(\alpha^2\big)^{N+1}-1}{\alpha^2-1}-\beta\frac{\big(\beta^2\big)^{N+1}-1}{\beta^2-1}\Bigg)\\ &=&\frac{1}{\alpha-\beta}\Big(\big(\alpha^2\big)^{N+1}-1-\big(\beta^2\big)^{N+1}+1\Big)\\ &=&\frac{1}{\alpha-\beta}\Big(\alpha^{2N+2}-\beta^{2N+2}\Big)\\ &=&F_{2N+2} \end{array}$$

For the second one you originally posted, "Sum the Fibonacci numbers $F_i$ with $i$ even": $$\begin{array}{rcl} \sum_{i=1}^NF_{2i}&=&\frac{1}{\alpha-\beta}\sum_{i=1}^N\big(\alpha^{2i}-\beta^{2i}\big)\\ &=&\frac{1}{\alpha-\beta}\Bigg(\sum_{i=0}^N\big(\alpha^2\big)^i-\sum_{i=0}^N\big(\beta^2\big)^i\Bigg)\\ &=&\frac{1}{\alpha-\beta}\Bigg(\frac{\big(\alpha^2\big)^{N+1}-\alpha^2}{\alpha^2-1}-\frac{\big(\beta^2\big)^{N+1}-\beta^2}{\beta^2-1}\Bigg)\\ &=&\frac{1}{\alpha-\beta}\Bigg(\frac{\alpha^{2N+2}-\alpha^2}{\alpha}-\frac{\beta^{2N+2}-\beta^2}{\beta}\Bigg)\\ &=&\frac{1}{\alpha-\beta}\Big(\alpha^{2N+1}-\alpha-\beta^{2N+1}+\beta\Big)\\ &=&\frac{1}{\alpha-\beta}\Big(\alpha^{2N+1}-\beta^{2N+1}\Big)-1\\ &=&F_{2N+1}-1 \end{array}$$