<s>[INST] First order recurrence relation I have to solve this  relation:
$$a_1 = k \\ a_n = \frac{10}{9} a_{n-1} + k + 1 - n$$
(k is constant)
How can I do it??
 [/INST] Use the generating function $A(x) = \sum_{n \ge 1}a_nx^n$ to capture the sequence $\{a_n\}$.
We are given (after adjusting indices $n \rightarrow n + 1$)
$$a_{n+1} = \frac{10}{9}a_n + k - n \text{ for } n \ge 1$$
Multiply by $x^n$ throughout and sum for all values of $n$ for which the recurrence holds.
$\begin{eqnarray}&\sum_{n \ge 1}a_{n+1}x^n &= \frac{10}{9}\sum_{n \ge 1}a_{n}x^n + k\sum_{n \ge 1}x^n - \sum_{n \ge 1}nx^n\\\implies&\frac{A(x) - a_1x}{x} &=\frac{10}{9}A(x) + k\frac{x}{1-x} - \frac{x^2}{(1-x)^2} - \frac{x}{1-x}\\\implies&\frac{9 - 10x}{9x}A(x) &= k + (k-1)\frac{x}{1-x} - \frac{x^2}{(1-x)^2}\\\implies &A(x) &=\frac{9kx}{9-10x} + \frac{9(k-1)x^2}{(1-x)(9-10x)} - \frac{9x^3}{(1-x)^2(9-10x)}\end{eqnarray}$
Partial fraction decomposition gives
$$A(x) = \frac{81(k-9)}{9-10x} + \frac{9(8-k)}{1-x} +\frac{9}{(1-x)^2}$$
We thus have,
$$\begin{align}a_n &= [x^n]A(x)\\&=[x^n]\frac{81(k-9)}{9-10x} + [x^n]\frac{9(8-k)}{1-x} +[x^n]\frac{9}{(1-x)^2}\\&=9(k-9)\left(\frac{10}{9}\right)^n + 9(8-k) + 9(n+1)\end{align}$$
Note: 


*

*The coefficient of $x^n$ in $\frac{c}{(1-\alpha x)^m} = c\binom{-m}{n}\alpha^n = c\binom{m + n - 1}{n}\alpha^n$

*The sum $\sum_{n \ge 1}nx^n = x\sum_{n \ge 1}nx^{n-1} = x\frac{d}{dx}\sum_{n \ge 1}x^n = x\frac{d}{dx}(\frac{x}{1-x})$

</s>