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

### 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
```
Associated Topics:
College Number Theory
High School Fibonacci Sequence/Golden Ratio
High School Number Theory

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