Fibonacci Proofs via Induction

  • Thread starter Thread starter cwatki14
  • Start date Start date
  • Tags Tags
    Induction Proofs
Click For Summary

Homework Help Overview

The discussion revolves around proving two statements related to Fibonacci numbers using mathematical induction. The first statement involves the sum of Fibonacci numbers up to Fn and its relation to Fn+2. The second statement concerns the sum of Fibonacci numbers at odd indices equating to a Fibonacci number at an even index.

Discussion Character

  • Exploratory, Mathematical reasoning, Problem interpretation

Approaches and Questions Raised

  • Participants discuss starting with base cases for the induction proofs, particularly considering n=3. There are attempts to apply the induction hypothesis and explore the implications of separating summations. Questions arise regarding the validity of the statements and the challenges encountered when moving terms between sides of the equation.

Discussion Status

The discussion is ongoing, with participants offering suggestions for base cases and expressing difficulties in progressing through the induction steps. Some guidance has been provided regarding the use of summation notation and recursion, but no consensus or resolution has been reached yet.

Contextual Notes

Participants are working under the constraints of needing to provide proofs via induction, which includes establishing base cases and induction steps. There is an emphasis on clarity and neatness in notation, particularly in relation to Fibonacci sequences.

cwatki14
Messages
56
Reaction score
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.
 
Physics news on Phys.org
You could start by trying a base case. Let n=3. What can you conclude from this? Is the statement valid?
 
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...
 
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.
 
So we I separate out the summation and apply the induction hypothesis to the other side I get:
\SigmaFj+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...
 
Simplify fn+1 + fn+2
 

Similar threads

Fibonacci sequence: what's wrong here?
  • · Replies 6 ·
Replies
6
Views
3K
Prove the typewriter sequence does not converge pointwise.
  • · Replies 2 ·
Replies
2
Views
6K
Do these two statements imply an underlying induction proof?
  • · Replies 7 ·
Replies
7
Views
1K
Drawing Fractals from IFS Equations
  • · Replies 14 ·
Replies
14
Views
2K
Is the Intersection of Nested Sets in a Complete Metric Space Nonempty?
  • · Replies 11 ·
Replies
11
Views
3K
Prove this inequality using induction
  • · Replies 2 ·
Replies
2
Views
2K
Lucas Numbers/ Fibonacci Numbers Proof
  • · Replies 3 ·
Replies
3
Views
8K
Strong Induction with Fibonacci numbers
  • · Replies 7 ·
Replies
7
Views
5K
Finding GCD with Fibonacci: Base Case
  • · Replies 1 ·
Replies
1
Views
2K
Proof by induction for rational function
  • · Replies 7 ·
Replies
7
Views
2K