Limit of a recursive sequence with an independent term that goes to 0

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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$

Answer 4

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

Answer 5

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.

Answer 6

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