Solve the recurrence relation $a_n={1\over2}a_{n-1}+1$, $a_1=1$

Question

Solve the recurrence relation: $$a_n=1/2a_{n-1}+1$$ With initial conditions: $$a_1=1$$ So far I have: $$Assume...a_n = r^n$$ $$r^n = {1\over2}r^{n-1} + 1$$ $$r={1\over2}+1$$ I have never had to solve one that didn't end with something like:$$r^2=Xr + Y$$ where you would move it all to one side and set equal to 0, then solve for r. Following that logic...$$r=1{1\over2}$$ I am unsure of where to go from here though... I also had the thought that the +1 makes this problem non-homogenous. If that is the case I am still unsure of how to solve the problem. Any help would be greatly appreciated.

Answer 1

For this kind of sequences (arithmetico-geometric sequences, defined by $a_n=pa_{n-1}+q$) you must first compute the fixed point of the function that defines the relation, since it is the candidate to be the limit, then make a substitution:

The fixed point of $f(x)=\frac12x+1$ is $x=2$. So set $b_n=a_n-2$. You get a geometric series: $$b_n+2=\frac12(b_{n-1}+2)+1, \enspace\text{whence}\enspace b_n=\frac12 b_{n-1}.$$

Thus $\;b_n=b_1\dfrac1{2^{n-1}}=-\dfrac1{2^{n-1}}$ and finally: $$a_n=2-\dfrac1{2^{n-1}}.$$

Answer 2

For this kind of recurrence relation, set $a_n=b_n+c$ and replace. So $$a_n=\frac 12 a_{n-1}+1$$ becomes $$b_n+c=\frac 12 (b_{n-1}+c)+1=\frac 12 b_{n-1}+\frac 12 c+1$$ This simplifies if we set $c=\frac 12 c+1$ that is to say $c=2$ and the new recurrence relation is just $$b_n=\frac 12 b_{n-1}$$