Fibonacci numbers pattern--induction

**yzc717** · September 7th 2009, 01:09 PM

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.

**galactus** · September 7th 2009, 01:35 PM

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

**yzc717** · September 7th 2009, 04:09 PM

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.

**galactus** · September 8th 2009, 03:30 AM

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.

**awkward** · September 8th 2009, 01:56 PM

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$

Thread: Fibonacci numbers pattern--induction

LinkBack

Thread Tools

Display

Fibonacci numbers pattern--induction

Similar Math Help Forum Discussions

Induction Proof- Fibonacci Numbers

Induction with Fibonacci Numbers

Induction and Fibonacci Numbers

Help with induction for Fibonacci Numbers

Help describing pattern (Fibonacci Numbers)

Search Tags