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??
 A: 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})$

A: hint: write out the expression for the next term:
$$
a_{n+1} = \frac{10}{9} a_n +k+1 -(n+1)
$$
and subtract. Then the $n$ term will cancel out, and you'll be able to construct a difference equation, $\Delta a_{n+1} = a_{n+1} - a_{n}$. Can you handle from here? 
EDIT: you should get an expression of the form
$$
\Delta a_{k+1} = r \Delta a_{k} + \gamma
$$
where $r, \ \gamma$ are constants. Now
$$
\Delta a_{k+1} = r \Delta a_{k} + \gamma = r^2 \Delta a_{k-1} + r \gamma + \gamma = r^3 \Delta a_{k-2} + r^2 \gamma +  r \gamma + \gamma\\
=\ldots = r^{k-1} \Delta a_2 + \Gamma
$$
here $\Gamma, \Delta a_2$ are constants you can easily find (hint: Geometric series). Now sum over $k$ on both sides. On LSH you have a telescoping sum, on RHS $r^k$ (hint: Geometric sum again). Be careful with the algebra though. 
