Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
High School Fibonacci Sequence/Golden Ratio
High School Sequences, Series

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search