Recursion with generating function.

Question

Using generating function determine $u_n$ $$u_{n+2} -6u_{n+1} + 9u_n = 2^n + n $$ I am asking for you to give me some advices. Thanks in advance.

Answer 1

at first solve the equation $$u_{n+2}-6u_{n+1}+9u_n=0$$ by the ansatz $u_n=q^n$ for the partical solution write $$2^nA+Bn+C$$

Answer 2

I’ll try to explain the general proceeding of solving recursions with generating functions using this example.

---

Write $u = \sum_{n=0}^∞ u_nX^n$ as well as $I = \sum_{n=0}^∞ X^n$. Observe that

• $I = \frac{1}{1 - X}$ ( – this is because $(1-X)I = \sum_{n=0}^∞ X^n - \sum_{n=1}^∞ X^n = 1$).
• $I[2X] = \frac{1}{1 - 2X}$ (– which follows from the above for $I[2X] = \sum_{n=0}^∞ (2X)^n = \sum_{n=0}^∞ 2^nX^n$).
• $I^2 = \sum_{n=0}^∞ (n+1)X^n$ (– this is because $\sum_{n=0}^∞ X^n·\sum_{n=0}^∞ X^n = \sum_{n=0}^∞ \Big(\sum_{k=0}^n X^{n-k}X^k\Big)$).

So, to resolve the recursion, you can instead solve the equation $$u - 6uX + 9uX^2 = I[2X]X^2 + I^2X^3 + cX + d,$$ for $u$, which – by comparing the coefficients of $X^n$ – for $n ≥ 2$ pointwise reads as $$u_n - 6u_{n-1} + 9u_{n-2} = 2^{n-2} + (n-2),$$ and for $n=1,0$ reads as $u_1 - 6u_0 = c+1$ and $u_0 = d$.

So choosing $d = u_0$ and $c = u_1 - 6u_0 - 1$ and using the identities way above, solve for $u$ in $$u(1 - 6X + 9X^2) = \text{right hand side}.$$ So you need to factorize $1 - 6X + 9X^2 = (1 - 3X)^2$. Because the inverse of $(1 - 3X)^2$ is $I[3X]^2$, you get $$u = I[3X]^2·(I[2X]X^2 + I^2X^3 + cX + d)$$ By substituting the definitions of all the terms, you get the recursion formula.

Lot of messy work, but a structural approach.