[Mathematics] Using generating functions to solve recurrences

[iironiic]

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:

.

[Reincarnate]

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]

[Zapmeister]

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

[iironiic]

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

Ahhh yes. Thank you!

[Reincarnate]

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

[smartdude1212]

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.