Use the generating function to solve a recurrence relation

Question

We have the recurrence relation $\displaystyle a_n = a_{n-1} + 2(n-1)$ for $n \geq 2$, with $a_1 = 2$.

Now I have to show that $\displaystyle a_n = n^2 - n +2$, with $n \geq 1$ using the generating function.

The theory in my book is scanty, so with the help of the internet I have the following:

$\displaystyle \sum_{n = 2} ^\infty (a_n - a_{n-1}) x^n = \sum_{n = 2} ^\infty a_n x^n - \sum_{n = 2} ^\infty a_{n-1} x^n = \sum_{n = 2} ^\infty a_n x^n - x \sum_{n = 2} ^\infty a_{n-1} x^{n-1} = (a(x) - a_1 x) - x(a(x)) = (a(x) - 2 x) - x(a(x)) = a(x) (1-x) - 2x$

But how I have to work out $\displaystyle \sum_{n = 2} ^\infty 2(n-1) x^n$ ?

If I have this, an expression for $a(x)$ can be found. How should $a_n$ be found from $a(x)$?

Answer 1

We have $a_n - a_{n-1} - 2n +2 = 0 \ (\star)$. Suppose the GF of $\langle a_n \rangle_{n\ge 1}$ is $f(x)$.

Then, $$\begin{align*} f(x) &= a_1 + &a_2 x& + a_3 x^2 + \cdots + a_n x^n + \cdots \\ -xf(x) &= &-a_1 x& - a_2 x^2 - \cdots - a_{n-1}x^n - \cdots\\ \frac{-2x}{(1-x)^2} &= &-2 x& - 4 x^2 \ \ - \cdots - 2n x^n + \cdots \\ \frac{2}{1-x} &= 2 + &2x& + 2x^2 \ \ + \cdots +2x^n + \cdots \end{align*}$$

Adding these up: $$f(x) -xf(x)-\frac{2x}{(1-x)^2} + \frac{2}{1-x} = (a_1 + 2) + \sum_{k=2}^\infty(a_k - a_{k-1} - 2k + 2)x^k.$$

But by $(\star)$, every term in the above infinite sum is $0$. Also our initial condition is $a_1 = 2$. So, $$f(x) (1-x) -\frac{2x}{(1-x)^2} + \frac{2}{1-x} = 4.$$

Solving for $f(x)$, we have $$f(x) = \frac{-4x^2+4x-2}{(x-1)^3} = \frac{-4x^2}{(x-1)^3} + \frac{4x}{(x-1)^3} - \frac{2}{(x-1)^3}.$$

The power series representation of $f(x)$ is then

$$f(x) = \sum_{n=0}^\infty \left( n^2-n+2 \right) x^n.$$

But the generating function for $\langle a_n \rangle$ was $f(x)$. So we can conclude that $$a_n = n^2 -n +2.$$

As you can see, using generating functions to solve recurrences is tedious, and requires a hefty amount of algebraic manipulation.

Answer 2

another observation is :$$a_n=a_{n-1}+2(n-1) ,\space \space \space a_1=2$$ $$\rightarrow a_n-a_{n-1}=2(n-1)\\$$ put $n=1,2,3,..(n-1)$ $$a_2-a_1=2(2-1 )=2(1)\\ a_3-a_2=2(3-1)=2(2)\\a_4-a_3=2(4-1)=2(3)\\...\\a_n-a_{n-1}=2(n-1)=2(n-1)\\$$no look at sum of them $$a_n-a_1=2(1)+2(2)+2(3)+...2(n-1)=\\2(1+2+3+4+...+(n-1))=2 \frac{(n-1)(n-1+1)}{2} \\so\\a_n-2=2\frac{n^2-n}{2}\\a_n=n^2-n+2$$

Answer 3

Note: Here is another approach using generating functions.

According to the recurrence relation

\begin{align*} a_1&=2\\ a_n&=a_{n-1}+2(n-1)\qquad\qquad n\geq 2 \end{align*} we set \begin{align*} A(x):=\sum_{n=1}^{\infty}a_nx^n \end{align*} and use the Ansatz \begin{align*} \sum_{n=2}^{\infty}a_nx^n&=\sum_{n=2}^{\infty}a_{n-1}x^n+2\sum_{n=2}^{\infty}(n-1)x^n\tag{1} \end{align*}

---

We observe \begin{align*} A(x)-2&=\sum_{n=1}^{\infty}a_nx^{n+1}+2\sum_{n=1}^{\infty}nx^{n+1}\tag{2}\\ &=xA(x)+2x^2\sum_{n=1}^{\infty}nx^{n-1}\\ &=xA(x)+2x^2\frac{d}{dx}\sum_{n=1}^{\infty}x^{n}\tag{3}\\ &=xA(x)+2x^2\frac{d}{dx}\left(\frac{1}{1-x}-1\right)\\ &=xA(x)+\frac{2x^2}{(1-x)^2}\tag{4} \end{align*}

Comment:

• In (2) we use the generating function $A(x)-a_1=A(x)-2$ at the LHS of (1) and do some index shifting at the RHS.

• In (3) we use the (formal) differential operator $\frac{d}{dx}$ applied to the geometric series $\frac{1}{1-x}$

We obtain from (4) by collecting terms with $A(x)$ at the LHS

\begin{align*} A(x)(1-x)&=2\left(1+\frac{x^2}{(1-x)^2}\right)\\ A(x)&=2\left(\frac{1}{1-x}+\frac{x^2}{(1-x)^3}\right)\tag{5} \end{align*}

Note: We have now derived a closed expression for $A(x)$ and it's time to harvest. We use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series. So, we can write $$a_n=[x^n]A(x)$$

and we get from (5) \begin{align*} a_n&=[x^n]A(x)\\ &=2[x^n]\frac{1}{1-x}+2[x^n]\frac{x^2}{(1-x)^3}\tag{6}\\ &=2[x^n]\sum_{n=0}^{\infty}x^n-2[x^{n}]x^2\sum_{n=0}^{\infty}\binom{-3}{n}(-x)^n\tag{7}\\ &=2+2[x^{n-2}]\sum_{n=0}^{\infty}\binom{n+2}{2}x^n\\ &=2+2\binom{n}{2}\\ &=n^2-n+2 \end{align*}

Comment:

• In (6) we use the formula for the binomial series $\frac{1}{(1-x)^\alpha}=\sum_{n=0}^{\infty}\binom{-\alpha}{n}x^n$

• In (7) we use $\binom{-\alpha}{n}(-1)^n=\binom{\alpha+n-1}{n}=\binom{\alpha+n-1}{\alpha-1}$