# Convergence of a recurrence

Given the recursive definition (starting with a positive integer) $$a_n = \frac{a_{n-1}}{2}+4$$ I am trying to find an explicit form and show that it approaches 8. So I started by writing it out, starting with an arbitrary value $a_1$, and one way to write this is $$\begin{matrix} \frac{\frac{\frac{a_1}{2}+4 }{2}+4}{2}+4 & \\ & \ddots \end{matrix}$$ or writing it term by term we could have $$\begin{matrix} \frac{a_1}{2}+4 \\ \frac{a_1}{4}+6 \\ \frac{a_1}{8}+7 \\ \frac{a_1}{16}+7.5 \\ \frac{a_1}{32}+7.75 \\ \end{matrix}$$ From the pattern it seems that an explicit formula for the $k^{th}$ term would be $$a_k = \frac{a_1}{2^k} + \left(8 - \frac{4}{2^{k-1}}\right)$$ which we could rewrite as $$a_k = 8 + \frac{a_1-8}{2^{k}}$$ and then to show convergence it is just $$\lim_{k \rightarrow \infty} \left[ 8 + \frac{a_1-8}{2^{k}} \right]= 8$$ This seems to work, but I simply looked for a pattern and guessed the explicit formula. My question is if there is a direct way to get from the recursive definition to the explicit one.

• Simple trick, if its going to converge on something, then we must have $\lim_{n\to\infty}(a_{n+1}=a_n)$ ie the definition of converging – Simply Beautiful Art May 12 '16 at 23:04

We have $$a_{n+1}-a_n = \frac{1}{2}\left(a_n-a_{n-1}\right)$$ hence $\{a_n\}_{n\geq 0}$ is a Cauchy sequence and $a_n\to L$. Such $L$ has to fulfill $$L = \frac{L}{2}+4$$ hence $L=\color{red}{8}$.

• Thanks Jack. I am reading on Cauchy sequences now, and I see this property about the differences between adjacent terms. So is it that the $L=\frac{L}{2}+4$ simply follows from the fact that $a_{n+1}-a_{n}$ is approaching zero? – Carser May 12 '16 at 22:48
• @Jed: exactly so, a Cauchy sequence is converging. – Jack D'Aurizio May 12 '16 at 23:04
• Well, not from $\;a_{n+1}-a_n\rightarrow0\;$ , since there are examples of non-converging sequences that fulfill this, but from the fact the sequence is Cauchy. – DonAntonio May 13 '16 at 0:10

HINT: a more direct way to show the convergence of $a_n$ is

$a_{n+1} = \frac{a_n}{2} + 4 = \frac{a_n+8}{2}$

If $8<a_0$, then $8<\frac{a_n+8}{2}<a_n$

If $a_0<8$, then $a_n<\frac{a_n+8}{2}<8$

Do you see how to turn this into the function for how quickly $a_n$ converges?

This can be solved with quadratics:

$$a_n=\frac{a_{n-1}}2+4\implies 2a_n-a_{n-1}-8=0\implies$$

This sequence is not homogeneosu, so we can do:

$$2a-a-8=0\implies a=8\implies 2(a_n-8)-(a_{n-1}-8)=0$$

and we now put $\;A_n:=a_n-8\;$ to get a homogeneous one that can be solved by means of its quadratic characteristic equation:

$$2A_n-A_{n-1}=0\implies 2r^2-r=0\implies r=0,\frac12\implies$$

the general solution is $\;A_n=B\cdot 0^n+C\cdot\cfrac1{2^n}=\cfrac1{2^n}C\;$

Suppose now that $\;A_0=K\implies \cfrac1{2^0}C=K\implies C=K\;$ , and thus our sequence is $\;A_n=\frac K{2^n}\;$, and going back to our original one:

$$a_n=A_n+8=\frac K{2^n}+8\xrightarrow[n\to\infty]{}8$$

Observe please that $\;K=A_0=a_0-8\implies a_0=K+8\;$ , but this first element is just unimportant in this case to get the final limit.

For the ((asub1/2+4)/2+4)... representation, set that equal to asubn=k as n approaches infinity. Then, consider that one less iteration (asubn-1) is also approaches k when n approaches infinity. Thus, k/2 +4=k, so k=8.

Simple trick, if its going to converge on something, then we must have $\lim_{n→\infty}(a_{n+1}=a_n)$ ie the definition of converging