3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – cjferes Sep 25 '14 at 18:23
  • $\begingroup$ Hey! You are right, I will edit. $\endgroup$ – Kris Sep 25 '14 at 18:32
  • 1
    $\begingroup$ The question is still not correctly stated. The correct sum is $F_{2n+2}$. $\endgroup$ – rogerl Sep 25 '14 at 18:39
  • 1
    $\begingroup$ And, computation of this and many other Fibonacci identities may be found here. $\endgroup$ – rogerl Sep 25 '14 at 18:41
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ +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. $\endgroup$ – Steven Stadnicki Sep 25 '14 at 19:33
1
$\begingroup$

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}

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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