Limit of a recursive sequence with an independent term that goes to 0 I have a recursive sequence where the first element is $a_{1} = 1$ and then $a_{n+1}= \frac12a_{n} + \frac{1}{n+1}$.
The first three terms are $a_{1} = 1 > a_{2} = \frac56 > a_{3} = \frac23$ so it seems reasonable to try to prove that the sequence is decreasing and then use the monotonicity of the sequence to try to prove that it has a finite or infinite limit. (This is my usual approach to recursive sequences.)
However, I don't know how to deal with the term $\frac1{n+1}$. Clearly $\lim \frac1{n+1} = 0$, but I don't know if I can erase it and solve $a_{n+1} = \frac12 a_{n} < \frac12 a_{n-1} = a_{n}$ to prove the monotonicity.
 A: And a new answer. We show by induction that $0\leq a_n\leq \frac{6}{n+1}$ for all $n$. This is true for $n=1$. If $a_n\leq \frac{6}{n+1}$, we get
$$a_{n+1}\leq \frac{3}{n+1}+\frac{1}{n+1}=\frac{4}{n+1} \leq \frac{6}{n+2}$$
and we are done.
A: Lemma: $a_n>{2\over n+1}$ for all $n \geq 2$
Base case: $a_2=1>{2\over3}$
Inductive process: $a_n>{2\over n+1}\implies a_{a+1}>{1\over n+1}+{1\over n+1}>{2\over n+2}$
Hence by induction the lemma is proven.
Now applying the lemma $a_{n+1}<\frac12a_{n}+\frac12a_{n}=a_n$ hence the sequence is decreasing. QED.
A: First prove a Lemma: $a_n > \frac{2}{n+1}$ for $n \geq2 $
When $n=2$, $a_2 = 5/6 > 2/3$
Now suppose $a_n > \frac{2}{n+1}$
then $a_{n+1} = \frac{a_n}{2}+ \frac{1}{n+1} > (\frac{1}{n+1})+\frac{1}{n+1} = \frac{2}{n+1} $
By induction, $a_n > \frac{2}{n+1}$ for all n 
Now we can prove that $a_n$ is decresing.
$a_{n+1}-a_n = \frac{a_n}{2}+ \frac{1}{n+1}-a_n = \frac{-a_n}{2}+ \frac{1}{n+1} < (-\frac{1}{n+1}) + \frac{1}{n+1} = 0$
so $a_n$ is decresing. By our Lemma, we also have $a_n \geq 0$, so we have a decresing sequence bounded below, thus it converges.
To find the limit, let $lim_{n\to \infty}  a_n = L$. By the recursive relation,
$L = L/2$ as $n\to \infty$
so $L = 0$
$lim_{n\to \infty} a_n = 0$
A: And another (marginally more general) approach:
Suppose $|a_{n+1}| \le {1 \over 2}|{a_n}| + K$. If we let $b_n = 2^n a_n$, this gives
$|b_{n+1}| \le |b_n| + K 2^{n+1}$ and so, with $n >m$, we have
$|b_n| \le |b_m|+K(2^{m+1}+\cdots+2^{n}) \le 2K 2^n$ and so
$|a_n| \le {1 \over 2^n} |a_m|+2K $. If we choose $N$ larger enough, we
see that we have $|a_n | \le 3K $ for $n \ge N$.
Now suppose $a_{n+1} = {1 \over 2}a_n + u_n$, where $u_n \to 0$.
Choose $\epsilon>0$ and let $N$ be such that $|u_n| < {1 \over 3} \epsilon$
for $n \ge N$. Then the above shows that there is some $N' \ge N$ such
that $|a_n| \le \epsilon$ for $n \ge N'$.
In particular, $a_n \to 0$.
A: Here is a complementary approach. We may obtain an explicit expression for $a_n$. From your initial relation
$$
a_{n+1}= \frac12a_{n} + \frac{1}{n+1}, \tag1
$$ multiplying by $2^{n+1}$ we get
$$
2^{n+1}a_{n+1}-2^{n}a_{n}=\frac{2^{n+1}}{n+1} \tag2
$$ then summing, terms telescope, giving

$$
a_{n}=\frac1{2^n}\sum_{k=1}^n\frac{2^k}k,\qquad n\geq1. \tag3
$$ 

One may observe that, as $n \to \infty$, we may prove that

$$
a_{n} \sim \frac1{2^n}\int_1^n\frac{2^x}x\:dx \sim \frac1{n \ln 2}.
$$

A: $$\begin{align}
a_{n+1}&=\frac 12 a_n+\frac 1{n+1}\\
\times 2^{n+1}:\qquad\qquad 
2^{n+1}a_{n+1}&=2^n a_n+\frac {2^{n+1}}{n+1}\\
\text {Put $b_r=2^ra_r$:}\qquad\qquad b_{n+1}-b_n&=\frac {2^{n+1}}{n+1}\\
\text {Summing by telescoping:}\qquad\qquad \quad 
b_n-b_1&=\sum_{r=2}^n\frac {2^r}r\\
\text {Noting that $b_1=2^1 a_1=2\cdot 1=\frac {2^1}1$:}\qquad \qquad\qquad 
b_n=2^na_n&=\sum_{r=1}^n\frac {2^r}r\\
a_n&=\frac 1{2^n}\sum_{r=1}^n\frac {2^r}r\end{align}$$
