Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 2 down vote accepted

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.

share|cite|improve this answer
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


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


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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.