03-13-2013, 08:37 AM | #1 |
D6 FFR Legacy Player
Join Date: Jan 2009
Age: 32
Posts: 4,342
|
[Mathematics] Using generating functions to solve recurrences
The question is to solve the following recurrence:
With . I am trying to use generating functions to solve this recurrence. I am aware that there are other ways to solve it (one way is to simply expand it and get the answer), but I want to practice using generating functions. I provided my work in the spoiler tags below. The images are huge so my apologies for that. I suppose my writing is pretty small, so at least it's clear to read. The idea is to set up the generating function by multiplying both sides by x^n and summing that from n = 1 to infinity. Let f(x) be defined as this generating function and rewrite the recursion in terms of f(x). Then I tried to rewrite f(x) as a generating function and then equate the coefficients. In the process of rewriting the generating function, I used partial fraction decomposition and the generalised binomial theorem. I relied on the fact that And then obtained a solution that does not agree with the initial conditions. Where did I go wrong? Please and thank you (: EDIT: I know that the correct answer is: Last edited by iironiic; 03-13-2013 at 08:42 AM.. |
03-13-2013, 09:09 AM | #2 |
x'); DROP TABLE FFR;--
Join Date: Nov 2010
Posts: 6,332
|
Re: [Mathematics] Using generating functions to solve recurrences
Just jotting down some stuff. I actually don't know generating functions that well either so this will be useful to learn.
I know that k(n) = 3k(n-1) - 3k(n-2) + k(n-3) Or matrix [0, 1, 0] [0, 0, 1] [1, -3, 3] exponentiated and then multiplied by vector X [0, 7, 15] |
03-13-2013, 09:29 AM | #3 |
FFR Player
Join Date: Sep 2012
Location: England
Posts: 466
|
Re: [Mathematics] Using generating functions to solve recurrences
in your third last line you have 3+n-1 chews n, or n+2 chews n
that's not (n+1)(n+2), you forgot to divide by 2. that gives you the right answer
__________________
Theorem: If you have a large enough number of monkeys, and a large enough number of computer keyboards, one of them will sight-read AAA death piano on stealth. And the ffr community will forever worship it. Proof Example ask me anything here mashed FCs: 329 |
03-13-2013, 09:32 AM | #4 |
D6 FFR Legacy Player
Join Date: Jan 2009
Age: 32
Posts: 4,342
|
Re: [Mathematics] Using generating functions to solve recurrences
|
03-13-2013, 10:02 AM | #5 |
x'); DROP TABLE FFR;--
Join Date: Nov 2010
Posts: 6,332
|
Re: [Mathematics] Using generating functions to solve recurrences
Dicked around on the Mathworld page here http://mathworld.wolfram.com/GeneratingFunction.html to read this shit a little more indepth, I think I understand now:
Okay so we have k_{n} = k_{n-1} + n + 6 with k_0 = 0 G(x) = <sum from n=1 to infinity> k_{n}*x^n G(x) = <sum from n=1 to infinity> (k_{n-1} + n + 6)*x^n G(x) = <sum from n=1 to infinity> k_{n-1}*x^n + <sum from n=1 to infinity> n*x^n + <sum from n=1 to infinity> for 6*x^n G(x) = x*G(x) + x * 1/(x-1)^2 + 6(x/(1-x)) G(x) = (6x^2 - 7x) / (x - 1)^3 = 7x + 15x^2 + 24x^3 + 34x^4 + 45x^5 + ... As for your closed form: k_{n} = <sum from k=1 to n> k + 6n = n(n+1)/2 + 6n = (n^2 + 13n)/2 Last edited by Reincarnate; 03-13-2013 at 10:09 AM.. |
03-13-2013, 10:45 AM | #6 |
2 is poo
Join Date: Sep 2005
Age: 32
Posts: 6,687
|
Re: [Mathematics] Using generating functions to solve recurrences
I just learned this stuff last semester in my combinatorics class and thought it was really cool.
|
Currently Active Users Viewing This Thread: 1 (0 members and 1 guests) | |
|
|