Proving the Fibonacci Sequence Using Induction

In summary, the conversation is discussing a problem to prove that F_{1}+F_{3}+F_{2n-1}=F_{2n}, with F being defined as Fibonacci numbers. The attempt at solving the problem involves using the induction proof and plugging in specific numbers to show that the equation holds. It is later clarified that F_2k+F_2k+1=F_2k+1+1 and this is what needs to be proven. However, there is confusion about the problem statement and the definition of F.
  • #1
kathrynag
598
0

Homework Statement


[tex]F_{1}+F_{3}+F_{2n-1}[/tex]=[tex]F_{2n}[/tex]

Homework Equations





The Attempt at a Solution


P(k+1):[tex]F_{2k-1}+F_{2k+1}[/tex]=[tex]F_{2k+2}[/tex]
 
Physics news on Phys.org
  • #2
What happened to F_1 and F_3?
 
  • #3
mutton said:
What happened to F_1 and F_3?

well, it's F_1+F_3+...+F_2n-1
 
  • #4
Then P(k + 1) needs to be changed accordingly.

What have you tried so far?
 
  • #5
I've tried plugging in numbers.
 
  • #6
And how did that work out?

The definition of Fibonacci numbers will be helpful in the induction proof.
 
  • #7
If I plug in 1, I just get F_1, so 1=1
If I plug in 2, I get F_3, so 1+2=F_4, 3=3
 
  • #8
kathrynag said:
well, it's F_1+F_3+...+F_2n-1

F-1+F-3+...+F_2k-1+F_2k+1
P(k)+F_2k+1
F_2k+F_2k+1

Now I'm stumped...
 
  • #9
kathrynag said:

Homework Statement


[tex]F_{1}+F_{3}+F_{2n-1}[/tex]=[tex]F_{2n}[/tex]

Homework Equations





The Attempt at a Solution


P(k+1):[tex]F_{2k-1}+F_{2k+1}[/tex]=[tex]F_{2k+2}[/tex]

kathrynag said:
well, it's F_1+F_3+...+F_2n-1
What was "F_1+ F_3+ ...+ F_2n-1"?

In your first post you said the problem was to prove that
[tex]F_{1}+F_{3}+F_{2n-1}[/tex]=[tex]F_{2n}[/tex]

Are you saying now it is actually to prove that
[tex]F_{1}+F_{3}+\cdot\cdot\cdot +F_{2n-1}[/tex]=[tex]F_{2n}[/tex]?
 
  • #10
kathrynag said:
F-1+F-3+...+F_2k-1+F_2k+1
P(k)+F_2k+1
F_2k+F_2k+1

Now I'm stumped...

Very close. What happens when 2 consecutive Fibonacci numbers are added?
 
  • #11
mutton said:
Very close. What happens when 2 consecutive Fibonacci numbers are added?

It equals the 3rd Fibonnacci number.
F_1+F-2=F_3

so F_2k+F_2k+1=F_2k+1+1
 
  • #12
And that's exactly what you wanted to show.
 
  • #13
Ok thanks!
 
  • #14
Sorry but maybe the problem is not properly stated? Are the F defined to be Fibonacci numbers?

Then F2n = F2n-1 + F2n-2

So if you are then asking also that

F2n = F2n-1 + F1 + F3

then

F2n-2 = F1 + F3

which is not making much sense.
 

1. What is the Fibonacci sequence?

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding numbers, starting with 0 and 1. The sequence is as follows: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, etc.

2. What is proof by induction?

Proof by induction is a mathematical method used to prove that a statement is true for all natural numbers. It involves two steps: a base case, where the statement is proven true for the first number, and an inductive step, where it is shown that if the statement is true for one number, it is also true for the next number.

3. How does Fibonacci proof by induction work?

Fibonacci proof by induction works by using mathematical induction to prove that the Fibonacci sequence follows a specific pattern. The base case is usually shown by proving that the first two numbers in the sequence are 0 and 1. Then, the inductive step is used to show that if the statement is true for the nth number, it is also true for the (n+1)th number. This proves that the statement is true for all numbers in the Fibonacci sequence.

4. What are the key steps in a Fibonacci proof by induction?

The key steps in a Fibonacci proof by induction are:
1. Proving the base case, usually by showing that the first two numbers in the sequence are 0 and 1.
2. Assuming the statement is true for the nth number in the sequence.
3. Using the inductive hypothesis to show that the statement is also true for the (n+1)th number in the sequence.
4. Concluding that the statement is true for all numbers in the Fibonacci sequence based on the inductive step.

5. Why is Fibonacci proof by induction important?

Fibonacci proof by induction is important because it provides a way to prove that a statement is true for all numbers in the Fibonacci sequence, without having to test every single number. This method is used in many areas of mathematics and computer science to prove statements about patterns or sequences that follow a specific rule.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
3K
  • Calculus and Beyond Homework Help
Replies
20
Views
382
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
992
  • Calculus and Beyond Homework Help
Replies
7
Views
2K
Replies
7
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
719
  • Calculus and Beyond Homework Help
Replies
1
Views
588
  • Calculus and Beyond Homework Help
Replies
6
Views
3K
Back
Top