Show the convergence of the recursive sequence and it's limit $ a_1:= 1 \ ,a_{n+1}=\frac{1}{2}a_n+1$ $$ a_1:= 1 \ ,a_{n+1}=\frac{1}{2}a_n+1$$
The first elements are:
$\quad a_{1} = 1$
$\quad a_{2} = \frac{3}{2}$
$\quad a_{3} = \frac{7}{4}$
$\quad a_{4} = \frac{15}{8}$
$\quad a_{5} = \frac{31}{16}$
The first elements show that $\quad a_{n} = \frac{2^n-1}{2^{n-1}} = 2^{1-n}(2^n-1)$ I would like in to use induction to continue my solution but I'm struggling at this point. How could I modify $2^{1-n}(2^n-1)$ to use induction and to show the limit?
Thank you for your help in advance.
 A: it's not needed to show an explicite formula. It's enough to prove that $(a_n) _n$ is a bounded and monotonically increasing sequence.
If $a_n<2$, we get $$a_{n+1}=\frac 12 a_n+1<\frac 12\cdot 2+1=2.$$
Since $a_1<2$, it holds $a_n<2$ for all $n$.
Further from $a_n<2$ follows $1>\frac 12 a_n$, which leads to
$$a_{n+1}=\frac 12 a_n+1>\frac 12 a_n+\frac 12 a_n=a_n.$$
Hence, $(a_n) $ is monotonically increasing.
Since $(a_n)$ is monotonically increasing and bounded ($a_0\leq a_n<2$ ), it converges. Let $ a$ be its limit. Then
$$a=\lim_{n\to\infty}\frac 12 a_n+1=\frac 12 a+1.$$
The only solution of this linear equation is $a=2$.
A: Perhaps a simpler representation is to split the fraction
$$
a_n = \frac{2^n-1}{2^{n-1}} = \frac{2^n}{2^{n-1}} - \frac{1}{2^{n-1}}
    = 2 - 2^{1-n} \to 2 \text{ as } n \to \infty
$$
To prove this, you can indeed use induction. You did the base case $n=1$ already, now just do the inductive step.
A: For induction, first assume that $a_n$ is true then prove that $a_{n+1}$ will also follow the same general formula on putting $n+1$ in place of $n$. It will come out to be true.
Next, as $n\to \infty$, the expression tends to $2$.
As general formula is $ \dfrac{2 (2^n -1)}{2^n} $ so $n\to \infty$ the $2^n$ term will dominate and the numerator and denominator will cancel, go song the limit as $2$.
