# Thread: A Fibonacci number problem

1. ## A Fibonacci number problem

How can we show that the following (recursive) statement, where $\displaystyle F_n$ is the $\displaystyle n$-th Fibonacci number, and $\displaystyle n \geq 1$, is true?

$\displaystyle \sum_{i=0}^{\lfloor \frac{n-1}{2} \rfloor} F_{n-2i}=F_{n+1}-1$

******

As this should be shown to be valid for every $\displaystyle n \in \mathbb{N}$, I believe we can use induction. The least $\displaystyle n$ which has to satisfy the above equation is $\displaystyle 1$, so we take the case when $\displaystyle n=1$ as basis. But,

$\displaystyle \sum_{i=0}^{\lfloor \frac{1-1}{2} \rfloor} F_{1-2i} \stackrel{\text{?}}{=} F_{1+1}-1$

$\displaystyle \sum_{i=0}^{0} F_{1-2i} \stackrel{\text{?}}{=} F_{2}-1$

$\displaystyle F_{1} \neq F_{2}-1$, because $\displaystyle F_1=1$, and $\displaystyle F_2-1=1-1=0$.

However, if we take the case when $\displaystyle n=2$ as basis, then the above statement is true:
$\displaystyle \sum_{i=0}^{\lfloor \frac{1}{2} \rfloor} F_{2-2i}=\sum_{i=0}^{0} F_{2-2i}=F_2=1=$

$\displaystyle F_{2+1}-1=F_3-1=2-1=1$

Is this problem wrongly posed? Should we show that $\displaystyle \sum_{i=0}^{\lfloor \frac{n-1}{2} \rfloor} F_{n-2i}=F_{n+1}-1$ is true for every $\displaystyle n \geq 2$ instead of $\displaystyle n \geq 1$?

And my next question would be how to proceed with the inductive step? I know we should use the fact that $\displaystyle F_n=F_{n-1}+F_{n-2}$ somewhere, but so far I couldn't show that the above is true for $\displaystyle k+1$ if we suppose it is valid form some $\displaystyle k \in \mathbb{N}$.

I'll be immensely grateful for any help.

2. Originally Posted by gusztav
How can we show that the following (recursive) statement, where $\displaystyle F_n$ is the $\displaystyle n$-th Fibonacci number, and $\displaystyle n \geq 1$, is true?

$\displaystyle \sum_{i=0}^{\lfloor \frac{n-1}{2} \rfloor} F_{n-2i}=F_{n+1}-1$
It is easier to think about this problem if you consider even and odd cases for $\displaystyle n$.

If $\displaystyle n$ is odd then $\displaystyle [\tfrac{n-1}{2}] = \tfrac{n-1}{2}$.
And the sum becomes $\displaystyle F_1+F_3+...+F_{n-2}+F_n = F_{n+1}-1$.

If $\displaystyle n$ is even then $\displaystyle [\tfrac{n-1}{2}] = \tfrac{n}{2} - 1$.
And the sum becomes $\displaystyle F_2 + F_4 + ... + F_{n-2} + F_n = F_{n+1} - 1$.

It is now easier to analyze this problem.

3. Originally Posted by ThePerfectHacker
It is easier to think about this problem if you consider even and odd cases for $\displaystyle n$.

If $\displaystyle n$ is odd then $\displaystyle [\tfrac{n-1}{2}] = \tfrac{n-1}{2}$.
And the sum becomes $\displaystyle F_1+F_3+...+F_{n-2}+F_n = F_{n+1}-1$.

If $\displaystyle n$ is even then $\displaystyle [\tfrac{n-1}{2}] = \tfrac{n}{2} - 1$.
And the sum becomes $\displaystyle F_2 + F_4 + ... + F_{n-2} + F_n = F_{n+1} - 1$.

It is now easier to analyze this problem.
Hmmm. I tried it this way, as you suggested, and broke the problem down into the cases when $\displaystyle n$ is even or odd. But in each of those cases, in the inductive step, there would be $\displaystyle n+1$, the number of different parity than that of $\displaystyle n$.

For example, if some $\displaystyle n$ is odd, then

$\displaystyle \sum_{i=0}^{\lfloor \frac{n-1}{2} \rfloor} F_{n-2i}=F_{n+1}-1$

becomes

$\displaystyle \sum_{i=0}^{\frac{n-1}{2} } F_{n-2i}=F_{n+1}-1$.

Let's say we have some odd number, for example n=5. In that case, $\displaystyle \sum_{i=0}^{\frac{5-1}{2} } F_{5-2i}=$$\displaystyle \sum_{i=0}^{2} F_{5-2i}=F_5 + F_3+F_1$, which is perfectly clear.
But in the inductive step, we take n=6 instead of n=5 and have $\displaystyle \sum_{i=0}^{\frac{6-1}{2} } F_{6-2i}=\sum_{i=0}^{\frac{5}{2} } F_{6-2i}$ which is meaningless (how to sum to $\displaystyle \frac{5}{2}$-th term?).

Or do we, in the inductive step, take $\displaystyle k+2$ (when $\displaystyle k$ is odd, then $\displaystyle k+2$ is also odd). But then, on the right side of the equation, $\displaystyle F_{n+1}-1$ should become $\displaystyle F_{n+3}-1$, while we need to have $\displaystyle F_{n+2}-1$ to prove this problem...

(Essentially, in the inductive proof we'd have to show that if
$\displaystyle \sum_{i=0}^{\lfloor \frac{k-1}{2} \rfloor} F_{k-2i}=F_{k+1}-1$ is true for some $\displaystyle k$, then it is also true for $\displaystyle k+1$.)

4. Say we wish to show $\displaystyle F_1 + F_3 + ... + F_n = F_{n+1} - 1$.

If it is true for $\displaystyle n$ we need to show it is true for $\displaystyle n+2$ (since we are inducting on the odds).
Adding $\displaystyle F_{n+2}$ on both sides gives,
$\displaystyle F_1+...+F_n + F_{n+2} = F_{n+1} + F_{n+2} - 1 = F_{n+3} - 1$
That is the inductive step.