(adsbygoogle = window.adsbygoogle || []).push({}); 1. The problem statement, all variables and given/known data

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 statment 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^{n}for all natural numbers n), we must prove bySTRONG(complete) inductionand weneed 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?

2. Relevant equations

N/A

3. The attempt at a solution

As shown above.

Any help is much appreciated!

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Mathematical induction: Fibonacci numbers

**Physics Forums | Science Articles, Homework Help, Discussion**