A Fibonacci Proof by Induction

Date: 06/05/98 at 09:20:23
From: Michael Wang
Subject: Fibonacci sequence: Proving by induction

Dear Doctor Maths,

I need to prove the following by induction:

   Let u_1, u_2, ..... be the Fibonacci sequence. Prove by induction 
   that for n > 0:

   u_(n-1) + u_(n-3) + u_(n-5) + ... < u_n

I am really stuck on this one because I don't even know where to 
begin. I am not sure how to prove that this is true for S_1 and then 
prove it is true for S_k and S_k+1.

Your help in the matter would be most appreciated.

Thank you, 
Michael

Date: 06/05/98 at 12:19:32
From: Doctor Rob
Subject: Re: Fibonacci sequence: Proving by induction

You didn't tell me the values of u_1 and u_2, so I am not sure which
Fibonacci sequence you mean. There are at least two different ones 
that are called by that name. This is important for establishing S_1.
I will assume that u_1 = 1, u_2 = 2.

One simple approach is to separate this into two cases, n even and 
n odd. First consider the case where n is odd, n = 2*k+1.

Then let S_k be the statement that:

   u_(2*k) + u_(2*k-2) + u_(2*k-4) + ... < u_(2*k+1).

Then S_1 is the statement that u_2 < u_3. That is true because u_2 = 2 
and u_3 = 3.

Assume S_k is true for some value of k. Then add u_(2*k) to both 
sides. On the right side, use the Fibonacci recursion to conclude that
u_(2*k-1) + u_(2*k) = u_(2*k+1) = u(2*[k+1]-1). Then you have proven
S_(k+1) by assuming S_k, so S_k implies S_(k+1). By the Principle of
Mathematical Induction, S_k is true for all k, so the statement you 
are trying to prove is true for all odd values of n.

Next consider the case where n is even, n = 2*k.

Now let T_k be the statement that:

   u_(2*k-1) + u_(2*k-3) + u_(2*k-5) + ... < u_(2*k).

Then T_1 is the statement that u_1 < u_2. That is true because u_1 = 1 
and u_2 = 2.

Assume T_k is true for some value of k. Then add u_(2*k+1) to both 
sides. On the right side, use the Fibonacci recursion to conclude that
u_(2*k) + u_(2*k+1) = u_(2*k+2) = u(2*[k+1]). Then you have proven
T_(k+1) by assuming T_k, so T_k implies T_(k+1). By the Principle of
Mathematical Induction, T_k is true for all k, so the statement you 
are trying to prove is true for all even values of n.

-Doctor Rob,  The Math Forum
Check out our web site! http://mathforum.org/dr.math/   

Date: 06/05/98 at 16:19:30
From: Doctor Anthony
Subject: Re: Fibonacci sequence: Proving by induction

For the first step:

u(3) + u(1) < u(4)  (yes, because u(4) = u(3) + u(2) and u(2) > u(1))
u(4) + u(2) < u(5)  (yes, because u(5) = u(4) + u(3) and u(3) > u(2))

Assume it is true for n = k:

   u(k-1) + u(k-3) + .... < u(k)  

Now add u(k+1) to both sides and we have:

   u(k+1) + u(k-1) + u(k-3) + ... < u(k) + u(k+1)

   u(k+1) + u(k-1) + u(k-3) + ... < u(k+2)

This is the same expression as we had before, except that k is 
replaced by k+2. So if the result is true for n = k it is also true 
for n = k+2. But it is true for n = 4, so it is true for n = 6, and if 
it is true for n = 6, then it is true for n = 8, 10, .... It is also 
true for n = 5 and so for n = 7, 9, 11, ... So the result is true for 
all positive integral values of n. 

-Doctor Anthony,  The Math Forum
Check out our web site! http://mathforum.org/dr.math/