# Thread: A Fibonacci number problem

1. ## A Fibonacci number problem

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

$\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 $n \in \mathbb{N}$, I believe we can use induction. The least $n$ which has to satisfy the above equation is $1$, so we take the case when $n=1$ as basis. But,

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

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

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

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

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

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

And my next question would be how to proceed with the inductive step? I know we should use the fact that $F_n=F_{n-1}+F_{n-2}$ somewhere, but so far I couldn't show that the above is true for $k+1$ if we suppose it is valid form some $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 $F_n$ is the $n$-th Fibonacci number, and $n \geq 1$, is true?

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

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

If $n$ is even then $[\tfrac{n-1}{2}] = \tfrac{n}{2} - 1$.
And the sum becomes $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 $n$.

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

If $n$ is even then $[\tfrac{n-1}{2}] = \tfrac{n}{2} - 1$.
And the sum becomes $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 $n$ is even or odd. But in each of those cases, in the inductive step, there would be $n+1$, the number of different parity than that of $n$.

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

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

becomes

$\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, $\sum_{i=0}^{\frac{5-1}{2} } F_{5-2i}=$ $
\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 $\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 $\frac{5}{2}$-th term?).

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

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

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

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