Prove by induction that $\sum\limits_{i=1}^n \frac{1}{n+i} \leq \frac{3}{4}$

Question

Prove by induction that $\sum\limits_{i=1}^n \frac{1}{n+i} \leq \frac{3}{4}$.

I have to prove this inequality using induction, I proved it for $n=1$ and now I have to prove it for $n+1$ assuming $n$ as hypothesis, but this seems impossible to me because the difference between the sum of $n$ and the sum of $n+1$ is a positive value. Adding a positive value on both sides of the inequality, I don't know how to prove that is always less than or equal to $\frac{3}{4}$.

Answer 1

Define $\displaystyle{S_n=\sum_{i=1}^n \dfrac{1}{n+i}}$. Then we have for every $n$ that:

\begin{align*} S_{n+1}-S_n&=\sum_{i=1}^{n+1}\dfrac{1}{n+1+i}-\sum_{i=1}^n \dfrac{1}{n+i}\\ &=\sum_{i=1}^{n+1}\dfrac{1}{n+1+i} - \left(\sum_{i=2}^n \dfrac{1}{n+i}\right)-\dfrac{1}{n+1}\\ &=\sum_{i=1}^{n+1}\dfrac{1}{n+1+i} - \left(\sum_{j=1}^{n-1} \dfrac{1}{n+1+j}\right)-\dfrac{1}{n+1}\\ &=\dfrac{1}{n+1+(n+1)}+\dfrac{1}{n+1+n}-\dfrac{1}{n+1}\\ &=\dfrac{1}{2n+1}-\dfrac{1}{2(n+1)}=\dfrac{1}{2(n+1)(2n+1)} \end{align*}

In particular, the sequence $S_n$ can also be defined by recurrence with the formula $$\begin{cases}S_1=\dfrac{1}{2}\\ S_{n+1}=S_n+\dfrac{1}{2(n+1)(2n+1)}\end{cases}$$

and so, $S_n$ is simply defined by the formula $$S_n=\sum_{i=1}^n \dfrac{1}{2n(2n-1)}.$$

Finally, showing that $S_n\leq \frac{3}{4}$ for all $n$ is the same as proving that the series $\displaystyle{\sum_{n=1}^\infty \dfrac{1}{2n(2n-1)}}$ converges to a number less than or equal to $\dfrac{3}{4}$.

If we focus on the infinite series, notice that $\dfrac{1}{2n(2n-1)}=\dfrac{1}{2n-1}-\dfrac{1}{2n}$, and so we have:

$$\sum_{n=1}^\infty \dfrac{1}{2n(2n-1)}=\sum_{n=1}^\infty \left(\dfrac{1}{2n-1}-\dfrac{1}{2n} \right)= \sum_{k=1}^\infty \dfrac{(-1)^{k+1}}{k}$$

I know the last series converges (by the test of alternating series), but I am just not sure about the value.

EDIT: AS lhf points out in his comment, the value of the last sum is $\log 2=0.69314\ldots$, which is surely less than $\dfrac{3}{4}$.

Answer 2

Note that you do not use induction in the above. Another way: Define $$S_n := \sum_{i=1}^n \frac{1}{n+i}$$ Then $$S_{n+1} = \sum_{i=1}^{n+1} \frac{1}{n+1+i} = \sum_{i=1}^{n+1} \frac{1}{n+(i+1)} = \sum_{i=2}^{n+2} \frac{1}{n+i}.$$ Hence $$S_{n+1} = S_n - \frac{1}{n+1} + \frac{1}{n+n+1} +\frac{1}{n+n+2}.$$ Now proceed...

Answer 3

Preliminary Result

Note that $$ \begin{align} s_{n+1}-s_n &=\sum_{k=1}^{n+1}\frac1{n+k+1}-\sum_{k=1}^n\frac1{n+k}\\ &=\sum_{k=2}^{n+2}\frac1{n+k}-\sum_{k=1}^n\frac1{n+k}\\ &=\frac1{2n+2}+\frac1{2n+1}-\frac1{n+1}\\ &=\frac1{2n+1}-\frac1{2n+2}\tag{1} \end{align} $$ Therefore, since $\frac1{2k}-\frac1{2k+1}\ge\frac12\left(\frac1{2k}-\frac1{2k+2}\right)$ $$ \begin{align} s_n &=\sum_{k=1}^n\left(\frac1{2k-1}-\frac1{2k}\right)\\ &=1-\sum_{k=1}^{n-1}\left(\frac1{2k}-\frac1{2k+1}\right)-\frac1{2n}\\ &\le1-\frac12\sum_{k=1}^{n-1}\left(\frac1{2k}-\frac1{2k+2}\right)-\frac1{2n}\\[3pt] &=\frac34-\frac1{4n}\tag{2} \end{align} $$

---

Inductive Proof

We will prove inductively that $$ \sum_{k=1}^n\frac1{n+k}\le\frac34-\frac1{4n}\tag{3} $$ Note that $(3)$ holds, with equality, for $n=1$.

Suppose that $$ \sum_{k=1}^n\frac1{n+k}\le\frac34-\frac1{4n}\tag{4} $$ Note that $\frac1{4n+4}\le\frac1{4n}-\frac1{2n+1}+\frac1{2n+2}\iff\frac1{2n+1}\le\frac12\left(\frac1{2n}+\frac1{2n+2}\right)$, which is true because $\frac1x$ is convex. Therefore, $$ \begin{align} \sum_{k=1}^{n+1}\frac1{n+k+1} &=\sum_{k=2}^{n+2}\frac1{n+k}\\ &=\color{#00A000}{\sum_{k=1}^n\frac1{n+k}}\color{#C00000}{-\frac1{n+1}+\frac1{2n+1}+\frac1{2n+2}}\\ &\le\color{#00A000}{\frac34-\frac1{4n}}\color{#C00000}{+\frac1{2n+1}-\frac1{2n+2}}\\[6pt] &\le\frac34-\frac1{4n+4}\tag{5} \end{align} $$ which completes the induction.

Answer 4

Let $$S_n=\sum_{i=1}^{n}\frac{1}{n+i}=\frac{1}{n}\sum_{k=1}^{n}\frac{1}{1+\frac{k}{n}}=H_{2n}-H_n.\tag{1}$$ We have $$ S_{n+1}-S_n = \frac{1}{2n+2}+\frac{1}{2n+1}-\frac{1}{n+1} = \frac{1}{(2n+1)(2n+2)} \tag{2}$$ hence $\{S_n\}_{n\geq 1}$ is an increasing sequence. Due to $(1)$ and Riemann sums, $$S_n \leq \lim_{n\to +\infty}S_n = \int_{0}^{1}\frac{dx}{1+x} = \log(2). \tag{3}$$ Over the interval $(0,1)$, the function $f(x)=x(1-x)$ is positive and $\leq \frac{1}{4}$, hence $$ \frac{1}{16}\geq \int_{0}^{1}\frac{x^2(1-x)^2}{1+x}\,dx = -\frac{11}{4}+4\log 2\tag{4} $$ and $$\log(2)\leq \frac{45}{64}<\frac{3}{4}.\tag{5}$$

Answer 5

Assuming $n>1$, $$\begin{align} \sum_{i=1}^n \frac 1{n+i} =\frac 1n \sum_{i=1}^n \frac 1{1+\frac in} &\color{red}<\int_0^1 \frac 1{1+x} \;\; dx = \bigg[\ln (1+x)\bigg]_0^1 =\ln 2=0.693 \color{red}<\frac 34\\ \Rightarrow \sum_{i=1}^n \frac 1{n+i}&\color{red}<\frac 34\qquad\blacksquare\end{align}$$