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