Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$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|improve this question

2 Answers 2

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

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

share|improve this answer

Your Answer

 
discard

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.