Author |
Topic: Identity Involving Fibonacci Number (Read 632 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Identity Involving Fibonacci Number
« on: Mar 15th, 2007, 2:59am » |
 Quote  Modify
|
Prove the identity (61) at this resource.
|
|
 IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Identity Involving Fibonacci Number
« Reply #1 on: Mar 15th, 2007, 9:24am » |
Quote Modify
|
The identity in question:
F_(n+1) = Sum _{ k = 0 to [n/2]} C(n-k, k)
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
|
| « Last Edit: Mar 15th, 2007, 9:24am by Aryabhatta » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Identity Involving Fibonacci Number
« Reply #2 on: Mar 15th, 2007, 10:35am » |
Quote Modify
|
on Mar 15th, 2007, 9:24am, 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: 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
|
|
Maybe, maybe... I am looking for a more elegant solution, though...
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Identity Involving Fibonacci Number
« Reply #3 on: Mar 15th, 2007, 12:39pm » |
Quote Modify
|
Ok. Here is another try
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)
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)
|
| « Last Edit: Mar 15th, 2007, 12:59pm by Aryabhatta » |
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Identity Involving Fibonacci Number
« Reply #4 on: Mar 15th, 2007, 1:05pm » |
Quote Modify
|
Here is another identity which the above method can be used to get:
Prove that
f(2n+1) = f(n+1) 2 + f(n)2
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Identity Involving Fibonacci Number
« Reply #5 on: Mar 15th, 2007, 1:07pm » |
Quote Modify
|
In fact, the general identity:
f(m+n) = f(m)*f(n+1) + f(n)*f(m-1)
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Identity Involving Fibonacci Number
« Reply #6 on: Mar 15th, 2007, 11:54pm » |
Quote Modify
|
on Mar 15th, 2007, 12:39pm, Aryabhatta wrote:Ok. Here is another try
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)
|
|
Exactly! That is the argument I asked for! Isn't it beatiful?
Well done, Aryabhatta! 
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Identity Involving Fibonacci Number
« Reply #7 on: Mar 16th, 2007, 12:24am » |
Quote Modify
|
Thanks! I am quite happy at having got this
Good that you did not accept the first proof... 
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print