First order recurrence relation

Question

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??

Answer 1

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})$

Answer 2

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.