Generating function to find $a_n$ formula

Question

Use generating function to find formula of $a_n$.

Given $a_0 = 1$, $a_1 = 2$, and $a_n = 2a_{n - 1} - a_{n - 2}$ for $n \geq 2$

Let $G(x) = \sum_{n \geq 0}a_nx^n$. Multiply both sides of $a_n = 2a_{n - 1} - a_{n - 2}$ by $x^n$ and sum over all $n$ for recurrence holds, that's for $n \geq 2$. We get $$\sum_{n \geq 2}a_nx^n = 2 \sum_{n \geq 2}a_{n - 1}x^n - \sum_{n \geq 2}a_{n - 2}x^n$$. Manipulate each term we got, $$\underbrace{\sum_{n \geq 2}a_nx^n + a_1x + a_0}_{=G(x)} -a_1x - a_0 = 2x(\underbrace{\sum_{n \geq 2}a_{n - 1}x^{n - 1} + a_0}_{G(x)} - a_0) - x^2\sum_{n \geq 2}a_{n - 2}x^{n - 2}$$ Simplify, we got $$G(x) - 2x - 1 = 2x(G(x) - 1) - x^2G(x)$$ Solve for $G(x)$, $$G(x) = 2xG(x) - 2x + 2x - x^2G(x) + 1$$ $$G(x)(x^2 - 2x + 1) = 1$$ $$G(x) = \frac{1}{x^2 - 2x + 1} = \frac{1}{(x - 1)^2}$$ I'm stuck here because it doesn't look like we can do partial fraction to find the coefficient $A$ and $B$, in fact, I think this is already in the form of partial fraction, however, I'm not sure how to generate a power series from here. Any suggestion?

Answer 1

$\dfrac1{(x-1)^2}=1+2x+3x^2+...$

---

Without generating function, you could say $a_n-a_{n-1}=a_{n-1}-a_{n-2}$,

so by induction $a_n-a_{n-1}=a_1-a_0=1,$

so $a_n-a_{n-1}+a_{n-1}-a_{n-2}+...+a_1-a_0=a_n-a_0=n$, so $a_n=n+1$.

Answer 2

You know that $\frac1{1-x}=\sum_{n\ge 0}x^n$; now take the derivative.

There is in fact a more general result:

$$\frac1{(1-x)^{k+1}}=\sum_{n\ge 0}\binom{n+k}n x^n=\sum_{n\ge 0}\binom{n+k}k x^n.$$

In your case $k=1$.

Answer 3

And if you believe that the binomial theorem works for any exponent:

$\begin{array}\\ \dfrac1{(1-x)^m} &=(1-x)^{-m}\\ &=\sum_{n=0}^{\infty} \binom{-m}{n}(-1)^nx^n\\ &=\sum_{n=0}^{\infty} (-1)^nx^n\dfrac{\prod_{k=0}^{n-1}(-m-k)}{n!}\\ &=\sum_{n=0}^{\infty} (-1)^nx^n(-1)^n\dfrac{\prod_{k=0}^{n-1}(m+k)}{n!}\\ &=\sum_{n=0}^{\infty} x^n\dfrac{\prod_{k=0}^{n-1}(m+n-1-k)}{n!}\\ &=\sum_{n=0}^{\infty} x^n\dfrac{\prod_{k=0}^{n-1}(m+n-1-k)\prod_{k=n}^{m+n-2}(m+n-1-k)}{n!\prod_{k=n}^{m+n-2}(m+n-1-k)}\\ &=\sum_{n=0}^{\infty} x^n\dfrac{\prod_{k=0}^{m+n-2}(m+n-1-k)}{n!\prod_{k=1}^{m-1}(m-k)}\\ &=\sum_{n=0}^{\infty} x^n\dfrac{\prod_{k=1}^{m+n-1}k}{n!\prod_{k=1}^{m-1}k}\\ &=\sum_{n=0}^{\infty} x^n\dfrac{(m+n-1)!}{n!(m-1)!}\\ &=\sum_{n=0}^{\infty} x^n\binom{m+n-1}{n}\\ \end{array} $