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.

  • $\begingroup$ $r={1\over2}+1$ is a fallacious deduction from what precedes it. $\endgroup$ – Gerry Myerson Oct 10 '15 at 23:22
  • $\begingroup$ What does the sequence $a_n$ converge to? $\endgroup$ – Gregory Oct 10 '15 at 23:25
  • $\begingroup$ @GerryMyerson If that is the case then how would I proceed in order to reach the correct answer? $\endgroup$ – Tejava Oct 10 '15 at 23:28
  • $\begingroup$ The usual method is, first solve the corresponding homogeneous recurrence, $a_n=(1/2)a_{n-1}$, then find a particular solution to the original recurrence, then put them together and use the initial value to find the undetermined constant. But surely whatever you are studying, you have some text or other materials that do examples like this? $\endgroup$ – Gerry Myerson Oct 10 '15 at 23:31

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


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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