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.

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

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

after this I have no idea how to proceed.

2. Here's a simple proof.

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

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

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

$f_{n+2}-1$

QED

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

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

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

And so on......

3. Originally Posted by galactus

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

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

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

This is where I have problems.

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

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

after this I have no idea how to proceed.

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

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

So, we have $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.

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

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

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

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