wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Identity Involving Fibonacci Number
        
(Message started by: Barukh on Mar 15^th, 2007, 2:59am)

Title: Identity Involving Fibonacci Number
Post by Barukh on Mar 15^th, 2007, 2:59am

Prove the identity (61) at this resource (http://mathworld.wolfram.com/FibonacciNumber.html).

Title: Re: Identity Involving Fibonacci Number
Post by Aryabhatta on Mar 15^th, 2007, 9:24am

The identity in question:

F_(n+1) = Sum _{ k = 0 to [n/2]} C(n-k, k)

[hide] I think Induction combined with the identity C(n+1,k) = C(n,k) + C(n, k-1) used appropriately should do it. In fact the figure on that page, helps you identify the way to do it [/hide]

Title: Re: Identity Involving Fibonacci Number
Post by Barukh on Mar 15^th, 2007, 10:35am

on 03/15/07 at 09:24:33, Aryabhatta wrote:

The identity in question:

F_(n+1) = Sum _{ k = 0 to [n/2]} C(n-k, k)

Thanks for putting it here!

Quote:

[hide] I think Induction combined with the identity C(n+1,k) = C(n,k) + C(n, k-1) used appropriately should do it. In fact the figure on that page, helps you identify the way to do it [/hide]

Maybe, maybe... I am looking for a more elegant solution, though...

Title: Re: Identity Involving Fibonacci Number
Post by Aryabhatta on Mar 15^th, 2007, 12:39pm

Ok. Here is another try

[hide]

f(n+1) is the number of ways of adding 1's and 2's so that they sum upto n.

Now count the same thing in a different way: dependent on the number of 2's.

If there are k 2's, there must be n-2k 1's. The number of ways of adding 1's and 2's to n, such that there are exactly k 2's is C(n-k,k)

Thus f(n+1) = sum C(n-k,k)

[/hide]

The good part about this is that, it lets you actually come up with the identity! (and can be used to come up with other such similar identities)

Title: Re: Identity Involving Fibonacci Number
Post by Aryabhatta on Mar 15^th, 2007, 1:05pm

Here is another identity which the above method can be used to get:

Prove that

f(2n+1) = f(n+1) ² + f(n)²

Title: Re: Identity Involving Fibonacci Number
Post by Aryabhatta on Mar 15^th, 2007, 1:07pm

In fact, the general identity:

f(m+n) = f(m)*f(n+1) + f(n)*f(m-1)

Title: Re: Identity Involving Fibonacci Number
Post by Barukh on Mar 15^th, 2007, 11:54pm

on 03/15/07 at 12:39:21, Aryabhatta wrote:

Ok. Here is another try

[hide]
f(n+1) is the number of ways of adding 1's and 2's so that they sum upto n.

Now count the same thing in a different way: dependent on the number of 2's.

If there are k 2's, there must be n-2k 1's. The number of ways of adding 1's and 2's to n, such that there are exactly k 2's is C(n-k,k)

Thus f(n+1) = sum C(n-k,k)
[/hide]

Exactly! That is the argument I asked for! Isn't it beatiful?

Well done, Aryabhatta! :D

Title: Re: Identity Involving Fibonacci Number
Post by Aryabhatta on Mar 16^th, 2007, 12:24am

Thanks! I am quite happy at having got this :D

Good that you did not accept the first proof... :)