Convergence of a recurrence

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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?

Answer 4

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.

Answer 5

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