Doctor John <joh### [at] homecom> wrote:
> Is there anywhere an elegant proof that Phi**n = F(n-1) + [F(n) * Phi]
> where F(x) is the value of the Fibonacci number x and Phi is the "Golden
> ratio" defined as Phi**2 - Phi - 1 = 0. I can demonstrate it with ease
> for an arbitrary value of n, but I seem to have forgotten the proof for
> all values of n. (BTW ** is the standard "raise to the power of"]
>
> A virtual bottle of your alcoholic liquid of choice to the poster of the
> most elegant proof.
>
> The judge's decision is final and lots of correspondence will be entered
> into.
>
> John
Not elegant.
Define F(n) as a Fibonacci sequence starting with 1, 1 etc.
Define Proposition_n: Phi^n = F(n)*Phi + F(n-1)
Phi^2 = 1*Phi + 1
Therefore Proposition_2 is true
Assume Proposition_n is true for all n st 2 \leq n \leq k
So  Phi^k = F(k)*Phi + F(k-1)
Phi^(k+1) = F(k)*Phi^2 + F(k-1)*Phi
          = F(k)*Phi + F(k) + F(k-1)*Phi
          = F(k+1)*Phi + F(k)
So Proposition_(k+1) is true
By induction Proposition_n is true for n \geq 2.

3rd entry on Googling fibonacci sequence is:
www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibnat.html

Post a reply to this message