1
$\begingroup$

$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.

3 Answers 3

2

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.

  • 0
    Yes, that's it! I imagine you can solve easily $y_n=y_{n-1}/a$.2012-11-08
1

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}\;.$