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

### Binet's Formula and Induction

```
Date: 11/28/2001 at 15:12:25
From: JT
Subject: Binet's Formula and Induction

Everywhere I look everyone keeps saying that Binet's formula can be
solved by induction. But what is induction, and can you prove Binet's
formula by induction?
```

```
Date: 11/28/2001 at 17:08:12
From: Doctor Rob
Subject: Re: Binet's Formula and Induction

Thanks for writing to Ask Dr. Math, JT.

The Principle of Mathematical Induction states that if a certain
statement that depends on n is true for n = 0, and if its truth for
n = k implies its truth for n = k+1, then the statement is true for
all integers n >= 0.

There is an equivalent form, which appears superficially to be
different. It states that if a certain statement that depends on n is
true for n = 0, and if its truth for all n <= k implies its truth for
n = k+1, then the statement is true for all integers n >= 0.

To apply this Principle in either form is to prove the statement "by
induction."

Binet's formula is

F(n) = (a^n-b^n)/(a-b).

Here F(n) is the nth Fibonacci number, defined by

F(0) = 0,
F(1) = 1,
F(n) = F(n-1) + F(n-2), for all n >= 2.

The quantities a and b are defined by the formulas

a = (1+sqrt[5])/2,
b = (1-sqrt[5])/2 = -1/a.

They are the two roots of the quadratic equation x^2 - x - 1 = 0.
(Check this!)

To prove Binet's Formula, first show that it is true for n = 0 and
n = 1.  Then for any k >= 1, assume it is true for all n <= k (in
particular for n = k and n = k-1), so that

F(k) = (a^k-b^k)/(a-b),
F(k-1) = (a^[k-1]-b^[k-1])/(a-b).

Now add these two equations together. The left-hand side becomes
F(k+1), according to the recursion defining the Fibonacci numbers.
Rearrange the right-hand side into the form

F(k+1) = (a^k+a^[k-1]-b^k-b^[k-1])/(a-b),
= (a^[k-1]*[a+1]-b^[k-1]*[b+1])/(a-b).

Now use the facts that a + 1 = a^2 and b + 1 = b^2, because a and b
are the roots of x^2 - x - 1 = 0. Then the above expression will
simplify into the form of Binet's Formula for n = k+1.

That establishes the hypotheses of the second form of the Principle of
Mathematical Induction. The conclusion of the Principle must therefore
hold, and Binet's Formula is true for all integers n >= 0.

Feel free to write again if I can help further.

- Doctor Rob, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Fibonacci Sequence/Golden Ratio
High School Logic
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