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

Post a reply to this message

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

JimT wrote:
> 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.
> 
Damn! I should have got that (((8(|) Doh!

> 3rd entry on Googling fibonacci sequence is:
> www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibnat.html
> 
Yup, seen that. Lots of good stuff there but I don't think he shows the 
proof above. iirc he only shows the definition.

John

Post a reply to this message

What set me moving was seeing the equation written as
Phi^2 = Phi + 1
which rapidly became
Phi^3 = Phi^2 + Phi etc.
I thought I saw Phi^2 = Phi + 1 on Ron Knott's page, but I've looked again and
can't find it.

The biggest problem with D'oh moments is they seem to come at decreasing
intervals with increasing age. :( in my case.

Post a reply to this message

I wish Phil had answered this. Then we could call him "Fibonacci Phil"!

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

JimT wrote:
> What set me moving was seeing the equation written as
> Phi^2 = Phi + 1
> which rapidly became
> Phi^3 = Phi^2 + Phi etc.
> I thought I saw Phi^2 = Phi + 1 on Ron Knott's page, but I've looked again and
> can't find it.
> 
> The biggest problem with D'oh moments is they seem to come at decreasing
> intervals with increasing age. :( in my case.
> 
> 

One wonders if there is a F(n) relationship, where F(n) is frequency of 
D'ohs per diem and n is age. I seem to have the same problem and I am 
but a spring chicken compared to Stephen ;-)

John

Post a reply to this message

JimT wrote:
> 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
> 

(((8(|)  (((8(|)

Just found the right page on Knott's site
http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibphiIndproof.html

John

Post a reply to this message

Doctor John 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"]

Since F(n) = ( phi^n - (1-phi)^n ) / sqrt(5), just plug in the formula 
for F(n) into your lemma equation and you'll have your proof.

Regards,
John

Post a reply to this message