Recursion with generating function. 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.
 A: 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$$
A: 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.
