Fibonacci Proofs via Induction

  • Thread starter cwatki14
  • Start date
  • #1
57
0
So I am looking at the following two proofs via induction, but I have not a single idea where to start.
The First is:
1. Suppose hat F1=1, F2=1, F3=2, F4=3, F5=5 where Fn is called a Fibonacci number and in general:
Fn=Fn-1+Fn-2 for n>/= 3. Prove that:
F1+F2+F3+...+Fn=(Fn+2)-1

Secondly is:
2. Prove that F1+F2+F5+...+F2n-1=F2n

Any help. I am looking for a proof via induction with a base case and induction step.
 

Answers and Replies

  • #2
614
0
You could start by trying a base case. Let n=3. What can you conclude from this? Is the statement valid?
 
  • #3
57
0
The base case part I think is more straight foward, but when I try to see if this hold for some k+1, things start to get tricky...
 
  • #4
614
0
I find it easier to work in summation notation here to keep it neat.
Take the sum from i=1 to n+1 of fi. You can take fn+1 out of the sum and then apply the induction hypothesis to the other term. Then use the recursion formula for the fibonacci sequence to simplify.
 
  • #5
57
0
So we I seperate out the summation and apply the induction hypothesis to the other side I get:
[tex]\Sigma[/tex]Fj+Fk+Fk-1=(Fk+2 + Fk+1) -1
So I basically want to move the Fk+1 from the RHS to the LHS, but I would have to subtract it, and that gets me nowhere...
 
  • #6
614
0
Simplify fn+1 + fn+2
 

Related Threads on Fibonacci Proofs via Induction

  • Last Post
Replies
1
Views
15K
  • Last Post
Replies
13
Views
3K
  • Last Post
Replies
3
Views
2K
Replies
11
Views
19K
  • Last Post
Replies
3
Views
3K
Replies
1
Views
4K
Replies
7
Views
9K
  • Last Post
Replies
11
Views
4K
  • Last Post
Replies
6
Views
1K
Replies
7
Views
4K
Top