# Induction proofs: fibonacci numbers

• LOLChris
In summary, the equations can be solved for n and k using the induction hypothesis that it is true for all s<n.
LOLChris

## Homework Statement

Use induction to prove this equation:

F(n+k) = F(k)F(n+1) + F(k-1)F(n)

## Homework Equations

F(0)=0 and F(1)=1
F(n)=F(n-1)+F(n-2)

## The Attempt at a Solution

Base: n=0, k=1
F(1)=(1*1)+(0*0)=1

True for n=k

k=k+1
F(2k+1) = F(k)F(k+2) + F(k-1)F(k+1)

Here is where I get stuck, I'm not sure how to manipulate this equation to show they are equal. I'm pretty sure I can solve it using only the relevant equations above.

Well if you pick your induction on for example on n, you get:

F(n+k+1)=F(n+k)+F(n+k-1)
You need to use here a different induction which asserts that if we assume that it's true for all s<n then it's true for s=n.

So this means that:
F(n+k)=F(k)F(n+1)+F(k-1)F(n)
F(n+k-1)=F(k)F(n)+F(k-1)F(n-1)
add them and you get the required equality, use F(n+1)+F(n)=F(n+2) and F(n)+F(n-1)=F(n+1).

LOLChris said:
True for n=k

k=k+1
F(2k+1) = F(k)F(k+2) + F(k-1)F(k+1)

Here is where I get stuck, I'm not sure how to manipulate this equation to show they are equal. I'm pretty sure I can solve it using only the relevant equations above.

Be careful! The k that you're using in your inductive hypothesis and the k in the original problem are not the same number

MathematicalPhysicist said:
Well if you pick your induction on for example on n, you get:

F(n+k+1)=F(n+k)+F(n+k-1)
You need to use here a different induction which asserts that if we assume that it's true for all s<n then it's true for s=n.

So this means that:
F(n+k)=F(k)F(n+1)+F(k-1)F(n)
F(n+k-1)=F(k)F(n)+F(k-1)F(n-1)
add them and you get the required equality, use F(n+1)+F(n)=F(n+2) and F(n)+F(n-1)=F(n+1).

Thanks, once I realized I could substitute for F(n+k) it was all downhill from there.

One question, when writing an induction proof for equations like this with two variables (n and k), should you prove 'n+1' or 'k+1'? Or both?

## 1. What are Fibonacci numbers?

Fibonacci numbers are a sequence of numbers in which each number is the sum of the two preceding numbers, starting with 0 and 1. The sequence goes like this: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and so on.

## 2. What is the purpose of using induction proofs for fibonacci numbers?

The purpose of using induction proofs for fibonacci numbers is to prove that a certain property or formula holds true for all numbers in the sequence. It is a mathematical technique used to prove statements about an infinite number of objects, such as the Fibonacci numbers.

## 3. How does induction proof work for fibonacci numbers?

Induction proof for fibonacci numbers works by first proving that the statement or formula holds true for the first few numbers in the sequence (usually 0 and 1). Then, assuming that the statement is true for a specific number, it can be shown to be true for the following number. This process is repeated until it can be shown that the statement is true for all numbers in the sequence.

## 4. What is the base case in an induction proof for fibonacci numbers?

The base case in an induction proof for fibonacci numbers is typically the first two numbers in the sequence, 0 and 1. These numbers serve as the starting point for the proof and are used to show that the statement holds true for the following numbers.

## 5. Are induction proofs the only way to prove properties of fibonacci numbers?

No, induction proofs are not the only way to prove properties of fibonacci numbers. Other methods such as direct proof, contradiction, and strong induction can also be used. However, induction proofs are a commonly used and effective technique for proving properties of fibonacci numbers.

• Calculus and Beyond Homework Help
Replies
15
Views
1K
• Calculus and Beyond Homework Help
Replies
1
Views
552
• Calculus and Beyond Homework Help
Replies
3
Views
598
• Calculus and Beyond Homework Help
Replies
1
Views
640
• Calculus and Beyond Homework Help
Replies
4
Views
684
• Calculus and Beyond Homework Help
Replies
1
Views
394
• Calculus and Beyond Homework Help
Replies
6
Views
522
• Calculus and Beyond Homework Help
Replies
2
Views
467
• Calculus and Beyond Homework Help
Replies
3
Views
479
• Calculus and Beyond Homework Help
Replies
6
Views
460