# Simple linear recursion

$x_n=\frac{x_{n-1}}{a}+\frac{b}{a}$ with $a>1, b>0$ and $x_0>0$

I tried to solve it using the generating function but it does not work because of $\frac{b}{a}$, so may you have an idea.

-

Hint: Let $x_n=y_n+c$, where we will choose $c$ later. Then $$y_n+c=\frac{y_{n-1}+c}{a}+\frac{b}{a}.$$ Now can you choose $c$ so that the recurrence for the $y$'s has no pesky constant term?

Remark: There is a fancier version of the above trick. Our recurrence (if $b\ne 0$) is not homogeneous. To solve it, we find the general solution of the homogeneous recurrence obtained by removing the $b/a$ term, and add to it some fixed particular solution of the non-homogeneous recurrence. In this case it is easy to find such a particular solution. Look for a constant solution.

-
I could choose c=$\frac{b}{a-1}$ ? – Montaigne Nov 8 '12 at 20:40
Yes, that's it! I imagine you can solve easily $y_n=y_{n-1}/a$. – André Nicolas Nov 8 '12 at 20:43

There are all sorts of ways to solve this. For instance, let $y_n=x_n-d$; then

$$y_n+d=\frac1a(y_{n-1}+d)+\frac{b}a=\frac{y_{n-1}}a+\frac{b+d}a\;,\tag{1}$$

so $$y_n=\frac{y_{n-1}}a+\frac{b+(1-a)d}a\;.$$ If we now set $d=\dfrac{b}{a-1}$, $(1)$ becomes $$y_n=\frac{y_{n-1}}a$$ with initial condition $y_0=x_0-d$. This is a simple exponential recurrence, so the solution is

$$y_n=\frac{y_0}{a^n}\;$$

and $$x_n=y_n+d=\frac{y_0}{a^n}+d=\frac{x_0-\frac{b}{a-1}}{a^n}+\frac{b}{a-1}=\frac{(a-1)x_0-b}{a^n(a-1)}+\frac{b}{a-1}\;.$$

-