Mathematical induction: Fibonacci numbers

[kingwinner]

Homework Statement

The Fibonacci numbers are defined by f(1)=1, f(2)=1 and for n>2, by f(n) = f(n-2) + f(n-1). Prove by mathematical induction that f(3n) is even for all natural numbers n.

Proof:
Base case: (n=1)
f(3) = f(2)+f(1) =1+1 =2 is even

Induction hypothesis: (suppose the statement is true for n=k, k≥1)
Suppose f(3k) is even. So f(3k) = 2m for some integer m.
Now we must show that the statement is true for n=k+1, i.e. f[3(k+1)] is even.

f[3(k+1)] = f(3k+3) = f(3k+2) +f(3k+1) = f(3k+1) + f(3k) + f(3k+1) = 2f(3k+1) + f(3k) = 2(f(3k+1) + m ) which is even since f(3k+1) is an integer.

Thus, the statement is true for all natural numbers n.
=========================================

I think there may have some flaws in this proof because this is what I found from other book on the section about mathematical induction:
"The Fibonacci sequence is defined recursively and depends on the previous TWO terms, so to prove statements regarding the Fibonacci sequence (e.g. f(n)≤2ⁿ for all natural numbers n), we must prove by STRONG(complete) induction and we need TWO base cases.

And this is exactly what I thought too. To prove statements about Fibonacci sequence by induction, we MUST use strong induction and need to verify two base cases since the sequence depends on the previous TWO terms. If we only verified ONE base case, it should be impossible to go on.

So is this proof correct or not? In particular, here are my concerns:
1) Do we need strong induction? Why or why not?
2) Do we need two base cases? Why or why not?

Homework Equations

N/A

The Attempt at a Solution

As shown above.

Any help is much appreciated!

 

[vela]

The proof is valid. You don't need strong induction because you're not relying on the hypothesis being true for more than one previous case to prove the k+1 case.

If you had a statement about F(n) and you relied on the hypothesis being true for F(k-1) and F(k) to show it holds for F(k+1), then you'd need strong induction and to show it's true for two base cases.

 

[kingwinner]

But the Fibonacci sequence is defined recursively and a term can be computed only when we know the values of the previous TWO terms. How come we do not need two base cases (n=1 and n=2)?

 

[vela]

Why do you need two base cases? Right now, your claim is that because F(n)=F(n-1)+F(n-2), you have to have two base cases. If you think about it, that's not an obvious leap. Specifically, for this proof, what exactly about the logic of the induction step breaks down if you don't have two base cases? You won't find anything because it doesn't require strong induction.

Try looking at a proof where strong induction was required. Why was strong induction required, and how does the proof break down if you don't have two base cases?

 

[kingwinner]

There is something that I don't understand...

Claim 1: f(n)≤2ⁿ for all natural numbers n.

Claim 2: f(3n) is even for all natural numbers n.

Why for claim 1, the proof requires two base cases(n=1, n=2), but for claim 2, the proof only requires one base case(n=1)? What is the difference between the nature of these 2 claims about Fibonacci numbers that leads to a difference in the way of proving these?

Thanks!

 

[vela]

That's what I'm suggesting you figure out. It's not the claims; it's the proofs. You have to look at the logic of the actual proofs to see why one needs only one base case and the other needs two.

 

[kingwinner]

OK!

For claim 1, f(2)=f(1)+f(0) and f(0) is undefined so it doesn't make sense, and we should check for one more base case n=2, so start at F(3)=F(2)+F(1), and the RHS is well defined.

For claim 2, f(3x2)=f(5)+f(4)=f(4)+f(3)+f(4)=f(3)+2f(4), all the terms on the RHS are defined, and 2f(4) is even no matter what f(4) is, so we only need one base case(n=1).

Is this the idea?

 

[vela]

For claim 1, f(2)=f(1)+f(0) and f(0) is undefined so it doesn't make sense, and we should check for one more base case n=2, so start at F(3)=F(2)+F(1), and the RHS is well defined.

Induction doesn't have to start with k=1. You could start with k=2 and avoid the f(0) problem, but you'd still need to show the hypothesis holds for two separate cases. It's not a question of whether the terms are defined or not.

For claim 2, f(3x2)=f(5)+f(4)=f(4)+f(3)+f(4)=f(3)+2f(4), all the terms on the RHS are defined, and 2f(4) is even no matter what f(4) is, so we only need one base case(n=1).

You're getting close, but again, it's not about whether terms are defined or not. When you deduce that f(6) is even, you rely on the assumption that f(3) is even, and that's the only assumption that the induction step needs. Does the induction step work in the same way for the other claim?