- The Powers of Phi Formula to prove
- What is a Proof By Induction?
- A Faulty Proof By Induction
- Proving this Formula by Induction
- Try these...

Phi^{n} = 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;

Fib(0)=0 and Fib(1)=1

and for Phi and phi we use the definitions
Fib(0)=0 and Fib(1)=1

Phi = | √5 + 1 | phi = | √5 – 1 | |

2 | 2 |

- 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.

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 "So we have to be particularly careful as to what the statement is (about n) that we are trying to prove.

Phi^{k} = Fib(k+1) + Fib(k) phi -- our starting assumption

and we want to show that Phi^{k+1} = Fib(k+2) + Fib(k+1) phi

must follow from
that assumption.Since the left hand sides differ by a factor of Phi, let's start by multiplying our assumed result by Phi on both sides:

Phi × Phi^{k} = Phi × ( Fib(k+1) + Fib(k) phi ) | |

Phi^{k+1} = Fib(k+1) Phi + Fib(k) Phi phi | |

Phi^{k+1} = Fib(k+1) Phi + Fib(k) | using Phi phi = 1 |

Phi^{k+1} = Fib(k+1) (1 + phi) + Fib(k) | since Phi = 1 + phi |

Phi^{k+1} = Fib(k+1) + Fib(k) + Fib(k+1) phi | by rearranging |

Phi^{k+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

Phi^{0} = Fib(0+1) + Fib(0) phi

which simplifies to
Ph^{0} = 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 Phi
^{n}= 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