Fibonacci Formula Inductive Proof

Date: 11/05/97 at 07:26:35
From: Alexander Joly
Subject: Fibonacci formula inductive proof

Hello!

I am stuck on a problem about the nth number of the Fibonacci 
sequence. I must prove by induction that
F(n) = (PHI^n - (1 - PHI)^n) / sqrt5

Here's what we usually do to prove something by induction:
1) Show that the formula works with n = 1.
2) Show that if it works for (n), then it will work for (n+1).

But the problem is:
We suppose F(n) is true, so F(n+1) is true.
But when I must prove it, I have to add another thing: F(n-1),
because F(n-1) + F(n) = F(n+1).

So here are the questions: 

Can I suppose TWO things are true, F(n) and F(n-1), to prove that 
F(n+1) is true?

How can I prove it is true for n = 1, since F(1) is DEFINED as equal 
to 1?

Here's what I've already done: I've successfully converted
(PHI^(n-1) - (1 - PHI)^(n-1)) / sqrt5 + (PHI^n - (1 - PHI)^n) / sqrt5
into (PHI^(n+1) - (1 - PHI)^(n+1)) / sqrt5

Thank you very much for your much-appreciated help!
An example of the Fibonacci formula inductive proof
would be very kind.

Alexander

Date: 11/05/97 at 13:25:14
From: Doctor Rob
Subject: Re: Fibonacci formula inductive proof

You have already done the hard part, which is in your next-to-last
paragraph.

Answer 1.  Yes, you can assume two things are true, but then you have 
to show that two starting values work. (Think about it.) An equivalent 
formulation of the Principle of Mathematical Induction is where you 
assume it is true for *all* values k with 1 <= k <= n, and use that to 
show it for n+1.  

Answer 2.  To prove it for n = 1, you have to show that

   1 = F(1) = (PHI - 1 + PHI)/sqrt(5).

You do this by using the fact that PHI = (1 + sqrt(5))/2. Substitute 
it in and check that it works. To prove it for n = 2, you have to  
show that

   1 = F(2) = (PHI^2 - [1 - PHI]^2)/sqrt(5).

You do this the same way.  By the way, this is also true for n = 0,

   0 = F(0) = (PHI^0 - [1 - PHI]^0)/sqrt(5),

for which you don't even need the formula for PHI.

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

Date: 11/05/97 at 15:31:47
From: Doctor Anthony
Subject: Re: Fibonacci formula inductive proof

                    1+sqrt(5)
Taking  PHI to be  -----------
                       2

we first check that the formula is true for n = 1 and n = 2

   F(1) = (1/sqrt(5))[(1+sqrt(5))/2 - 1 -(1+sqrt(5))/2] 

        = (1/sqrt(5))[1/2 + sqrt(5)/2 - 1/2 + sqrt(5)/2]

        = 1/sqrt(5)[sqrt(5)]

        = 1

    F(2) = (1/sqrt(5))[PHI^2 - (1-PHI)^2]

         = (1/sqrt(5)[PHI^2 - 1 + 2 PHI - PHI^2]

         = (1/sqrt(5))[2 PHI - 1]

         = (1/sqrt(5)[1+sqrt(5) - 1]

         = 1

So the formula is correct for n=1 and n=2.  Now assume it is true for 
all terms UP TO some other value n.

If we take

            1      sqrt(5)+1             1 - sqrt(5)
F(n+1) = -------[ (--------- )^(n+1) - ( ----------- )^(n+1)]
         sqrt(5)        2                      2


By taking out a factor   (sqrt(5)+1)^2
                          ---------       from the first term and 
                              2^2
  (1-sqrt(5))^2
   ----------      
      2^2

from the second term and then squaring out these brackets it is easy 
to show that  F(n+1) = F(n) + F(n-1).

So if the expression is true for n and n-1, it is also true for n+1.  
But it is true for n=1 and n=2, hence it must be true for n=3. So true 
for n=2 and n=3 it is true for n=4. Thence to n=5, n=6, n=7 and so on 
to all positive integer values of n. 
       
-Doctor Anthony,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/   

Date: 11/10/97 at 11:55:23
From: Joly
Subject: Re: Fibonacci formula inductive proof

Dear Dr. Rob,

I give up, Doctor Rob. I must use three values (F(n), F(n-1) and 
F(n+1)), but I can't find the way to justify this use of the 
induction. I know I have to show that two starting values work, but 
this is where I am stuck. I don't know how to show it.

Thank you very much for your time!

Date: 11/10/97 at 12:44:31
From: Doctor Rob
Subject: Re: Fibonacci formula inductive proof 

I'm sorry that my previous answer was not sufficient to solve your 
problem. As I understand the current state of the problem, you need 
the following theorem to finish it:

Theorem:  If P(n) is a statement involving the variable n, and if P(1) 
is true, P(2) is true, and the implication P(k) & P(k+1) ==> P(k+2) is 
true, then P(n) is true for all n >= 1.

Proof:  We will prove this using the Principle of Mathematical 
Induction.

Let Q(n) be the statement "P(n) is true and P(n+1) is true." Then Q(1)
holds by hypothesis. Given Q(k) is true, we know that P(k) and P(k+1) 
are true. Using the implication from the hypotheses of the theorem, 
P(k+2) is also true, so P(k+1) and P(k+2) are both true. Thus Q(k+1) 
is true. This means that Q(k) ==> Q(k+1). Thus by the Principle of 
Mathematical Induction, Q(n) is true for all n >= 1.  Q(n) ==> P(n), 
so P(n) is true for all n >= 1.  Q.E.D.

This is the justification you need to use your "double-step" 
induction. See how the need for Q(1) to be true forces us to make sure 
that both P(1) and P(2) are true, so we have a two-part start for the 
induction.

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

Date: 11/10/97 at 14:21:46
From: DJoly
Subject: RE: Thanks, Doctor Rob!

Thank you very much! Your answers were very complete. This is all 
people could expect from Dr. Math's service!

Alexander