# How to solve a recurrence relation with generating functions?

I don't really understand how to solve (with generating functions) for the recurrence relation of $$a_n = a_{n-1}+2(n-1)$$ with initial conditions of $$a_1 = 2$$ when $$n \geq 2$$

This is what I was thinking, \begin{align*} g(x) &= a_0x^0+a_1x^1+a_2x^2+...+a_rx^r+...\\ g(x) &= a_0 + a_1x^1 + \sum^{\infty}_{n=2}a_nx^n\\ g(x) &= 1 + 2x + \sum^{\infty}_{n=2}{(a_{n-1}+2(n-1))x^n}\\ g(x) &= 1 + 2x + \sum^{\infty}_{n=2}a_{n-1}x^n + \sum^{\infty}_{n=2}(2n-2)x^n\\ g(x) &= 1 + 2x + x\sum^{\infty}_{n=1}a_{n-1}x^{n-1} + \sum^{\infty}_{n=2}2n x^n - \sum^{\infty}_{n=2}2x^n\\ g(x) &= 1 + 2x + x\sum^{\infty}_{m=1}a_{m}x^{m} + \sum^{\infty}_{n=2}2 \binom{n}{1}x^n - \sum^{\infty}_{n=2}2x^n\\ g(x) &= 1 + 2x + x(g(x) - a_0) + \sum^{\infty}_{n=2}2 \binom{n}{1}x^n - \sum^{\infty}_{n=2}2x^n\\ \end{align*}

• A linear recurrence relation and two initial conditions? That's strange, but easily fixable. – Jack D'Aurizio Dec 12 '18 at 3:09
• Fixed it -- thanks! – Violet Jung Dec 12 '18 at 3:22

You certainly do not need generating functions for solving $$a_n-a_{n-1}=2(n-1)$$: it is enough to sum both sides on $$n=1,2,\ldots,N$$ to get that $$a_n$$ depends on $$\sum_{k=1}^{n}2(k-1)$$. The only issue in your case is that the given values of $$a_0$$ and $$a_1$$ do not agree with the given recurrence relation. So, let us assume $$a_0=\color{red}{2}$$ and $$a_{n}=a_{n-1}+2(n-1)$$ for any $$n\geq 1$$. By denoting as $$f(x)$$ the following generating function $$f(x)=\sum_{n\geq 0} a_n x^n = 2+\sum_{n\geq 1}a_n x^n$$ we have $$x\cdot f(x) = \sum_{n\geq 0} a_n x^{n+1} = \sum_{n\geq 1} a_{n-1} x^n$$ hence by the recurrence relation $$(1-x) f(x) = 2+2\sum_{n\geq 1}(n-1)x^n = 2+\frac{2x^2}{(1-x)^2}$$ where the last identity follows from stars and bars in the form $$\frac{1}{(1-x)^{m+1}}=\sum_{n\geq 0}\binom{n+m}{m}x^n.$$ Since we have $$f(x) = \frac{2}{1-x}+\frac{2x^2}{(1-x)^3}$$ stars and bars also gives $$a_n = [x^n]f(x) = 2-n+n^2.$$
• @MathNewbie: you may just start with $a_1=2$, the linear recurrence relation and the generating function defined as a sum over $n\geq 1$. – Jack D'Aurizio Dec 12 '18 at 3:18
• $a_1=2$ makes sense: a circle (simple closed curve) divides the plane into two connected components (Jordan's theorem). What is debatable is to assign a value to $a_0$. – Jack D'Aurizio Dec 12 '18 at 3:29