This is an option extra page summarizing the method of Proof By Induction, applied to a particular Fibonacci
number formula. We show how not to use the method also as well as the complete proof of the formula.
Contents of this page
The icon means there is a
Things to do investigation at the end of the section.
The Powers of Phi Formula to prove
The formula we will prove is
Phin = Fib(n+1) + Fib(n) phi
We assume the standard definition of Fib(n):
Fib(n+2)=Fib(n+1)+Fib(n) for all n>0; and for Phi and phi we use the definitions
Fib(0)=0 and Fib(1)=1
|Phi = ||√5 + 1
||phi = ||√5 – 1|
What is a Proof By Induction?
A proof by induction involves two steps:
- Proving that IF the above formula is true for
any particular value of n, let's say n=k,
then it must automatically follow that it isrue for k+1 too.
Since (k+1) is another particular value, the same argument shows the formula
is therefore true for k+2.
"By induction" we can therefore reason that it will be true for all following values of n
from k onwards.
Note that we assume the formula is true for n=k and, on that basis, show that it must
inevitably be true for the next larger value k+1.
This assumption f(that the formula is true for n=k in particular)
is called the Inductive Assumption. It is not the same as assuming the formula is true for
all n, since we are only assuming it is true for one particular value of n, namely n=k.
The proof that "IF the formula is true for n=k THEN it must also be true for n=k+1 also"
must be sufficiently general that it applies to all values of k, that is, it
does not rely on specific values of k to work.
- There must be a value of n for which the formula can be shown to be true.
This value will start off the "induction" process. So, for the formula to be true for
all n we need the starting value to be n=1 or perhaps n=0.
A Faulty Proof By Induction
Failure to observe these two conditions fully gives rise to faulty induction "proofs".
For instance, here is a "proof" that All cars are red.
We show a faulty application of proof by induciton to the
statement All sets of n cars are red cars. and show it is true for all
values of n:
- Suppose that we have a specific instance where it is true: n=k.
Our assumption is that ALL sets of k cars contain only red cars.
So let's take any other car
and add it in to make a set of k+1 cars.
We need to show it is red too.
To show this new set contains only red cars means we have to show the new car is red too.
We do this by considering a subset of the new set formed by taking out any other car from the set,
leaving a set of size n containing the original assumption
that all sets of size k are of red cars then this set is too.
But that set contains the new car and so we have shown, on the basis if the assumption
that the new car is red too.
- My car is red so I can find a set of size 1 for which the statement is true.
So where has this "proof" gone wrong since clearly there are cars of other colours than red?
Well, although there is no fault in the
reasoning of the inductive part of the argument (stage 1 above), the second part is not
always true. Whilst my car is red, my neighbour's car is white, so it wouldn't work for him!
We cannot verify the second condition, that the statement "All sets of 1 car are red cars"
is always true.
So we have to be particularly careful as to what the statement is (about n) that we are trying to prove.
Proving this Formula by Induction
First, assume it is true for n=k, that is that
Phik = Fib(k+1) + Fib(k) phi -- our starting assumption
and we want to show that
Phik+1 = Fib(k+2) + Fib(k+1) phi must follow from
Since the left hand sides differ by a factor of Phi, let's start by multiplying our
assumed result by Phi on both sides:
Notice that the above argument would work no matter what the value of k is.
| Phi × Phik = Phi × ( Fib(k+1) + Fib(k) phi )|| |
| Phik+1 = Fib(k+1) Phi + Fib(k) Phi phi|| |
| Phik+1 = Fib(k+1) Phi + Fib(k) || using Phi phi = 1|
| Phik+1 = Fib(k+1) (1 + phi) + Fib(k) || since Phi = 1 + phi|
| Phik+1 = Fib(k+1) + Fib(k) + Fib(k+1) phi|| by rearranging|
| Phik+1 = Fib(k+2) +Fib(k+1) phi||by the Fibonacci Rule|
Secondly, we need to find a starting value for n for which the formula is true.
When n=0, we have
Phi0 = Fib(0+1) + Fib(0) phi which simplifies to
Ph0 = 1 + 0 phi = 1
which we know is true.
So the two parts of our proof by induction are now complete.
Things to do
- Prove that Phin = Phi Fib(n) + Fib(n-1)
- Prove that the sum of the Fibonacci numbers from Fib(1) up to Fib (n) is Fib(n+2)-1 (proved by Lucas in 1876)
Hint: in the inductive step, add "the next term" to both sides of the assumption.
- Prove that the sum of the squares of the Fibonacci numbers from Fib(1)2 up to Fib(n)2
is Fib(n) Fib(n+1) (proved by Lucas in 1876)
Hint: in the inductive step, add "the square of the next Fibonacci number"
to both sides of the assumption.
- Many of the formula on the Fibonacci and Golden Section formulae page can
be proved by induction. Try some!
© 2003 Dr Ron Knott
created 26 November 2003