1. ## Fibonacci numbers pattern--induction

Prove that the sum of the first n Fibonacci numbers is equal to the (n+2)nd fibonacci number minus one.

Base case: n=1
1st Fib# =1 =third fib# -1=2-1 True

This is where I have problems.

$\displaystyle f_{1}+f_{2}+f_{3}+....+f_{n}+f_{n+1}$

$\displaystyle =f_{n+2}-1+f_{n+1}$

after this I have no idea how to proceed.

2. Here's a simple proof.

$\displaystyle f_{1}+f_{2}+f_{3}+.....+f_{n}$

$\displaystyle =(f_{3}-f_{2})+(f_{4}-f_{3})+(f_{5}-f_{4})+....+(f_{n+2}-f_{n+1})$

$\displaystyle =f_{n+2}-f_{2}$

$\displaystyle f_{n+2}-1$

QED

If you want to try induction, try $\displaystyle f_{1}+f_{2}+f_{3}+....+f_{n}+f_{n+1}$

$\displaystyle =(f_{3}-f_{2})+(f_{4}-f_{3})+(f_{5}-f_{4})+....+(f_{n+2}-f_{n+1})+(f_{n+3}-f_{n+2})$

$\displaystyle =f_{n+3}-f_{n+1}-f_{2}$

And so on......

3. Originally Posted by galactus

$\displaystyle =(f_{3}-f_{2})+(f_{4}-f_{3})+(f_{5}-f_{4})+....+(f_{n+2}-f_{n+1})+(f_{n+3}-f_{n+2})$

$\displaystyle =f_{n+3}-f_{n+1}-f_{2}$

And so on......
I still don't get these.

This is where I have problems.

$\displaystyle f_{1}+f_{2}+f_{3}+....+f_{n}+f_{n+1}$

$\displaystyle =f_{n+2}-1+f_{n+1}$

after this I have no idea how to proceed.

4. That's because $\displaystyle f_{2}=1$ and it is a telescoping series so everything cancels except those terms.

Note that $\displaystyle f_{n+3}-f_{n+1}=f_{n+2}$

So, we have $\displaystyle f_{n+2}-1$, as before, when using induction.

5. Originally Posted by yzc717
Prove that the sum of the first n Fibonacci numbers is equal to the (n+2)nd fibonacci number minus one.

Base case: n=1
1st Fib# =1 =third fib# -1=2-1 True

This is where I have problems.

$\displaystyle f_{1}+f_{2}+f_{3}+....+f_{n}+f_{n+1}$

$\displaystyle =f_{n+2}-1+f_{n+1}$

after this I have no idea how to proceed.
You are almost done.

$\displaystyle =f_{n+2}-1+f_{n+1} = f_{n+3}-1$