Wednesday, December 17, 2008

Similarity of Recursive formulas for Derangment and Fibonacci

Its about 13:04 and I am standing in front of student center. I came to my office early in the morning around 9 am. Helped set up my parent's wii through the web cam. Though one thing still remains - i.e getting the video output. Its funny that I only noticed yesterday that the recursive formulas for derangement numbers and Fibonacci number are so similar. The derangement numbers are D(n) = (n-1)(D(n-1)+D(n-2)). While the Fibonacci numbers are
F(n) = F(n-1)+F(n-2). Let me write them together, so you can see it more clearly.

D(n) = (n-1)(D(n-1)+D(n-2))
F(n) = F(n-1)+F(n-2)

To derive the generating function from these its easier to use exponential generating function for D(n) and ordinary generating function for F(n). For D(n) it is the nth coefficient of exp(-z)/(1-z) and for F(n) its the nth coefficient of x/(1-x-x^2)

0 Comments:

Post a Comment

<< Home

Site Meter