4

I'm trying to solve these induction exercises proposed by the department of mathematics of Oxford University. I don't know how to give a valid proof for the third one which says the following:

Prove that for $n \in \mathbb{N}^{\ge 1}$: $$ \sqrt{n} \le \sum_{k=1}^n \frac{1}{\sqrt{k}} \le 2 \sqrt{n} - 1 $$

My first approach has been to convert the summation into a function in terms of $n$ so that I could find the maximum and minimum values in the interval. However, there doesn't seem to be an easy way to express the summation as a function. Thanks in advance!

Martin Sleziak
  • 53,687
IOS_DEV
  • 539
  • 3
    The induction start is easy. Then it is sufficient that you show $$\sqrt{n+1} - \sqrt{n} \leqslant \frac{1}{\sqrt{n+1}} \leqslant 2(\sqrt{n+1}-\sqrt{n}).$$ – Daniel Fischer Jul 28 '14 at 18:57
  • See also: http://math.stackexchange.com/questions/509840/use-induction-to-prove-that-1-frac-1-sqrt2-frac-1-sqrt3, http://math.stackexchange.com/questions/420733/proving-that-frac1-sqrt1-frac1-sqrt2-cdots-frac1-sqrt, http://math.stackexchange.com/questions/56335/proving-sum-limits-k-1n-frac1-sqrtk-ge-sqrtn-with-induction (and maybe other posts on this site). – Martin Sleziak Aug 13 '14 at 20:31

2 Answers2

3

Since $$ \sqrt{k+1}-\sqrt{k}=\frac1{\sqrt{k+1}+\sqrt{k}}\tag{1} $$ we have $$ \frac1{2\sqrt{k+1}}\le\sqrt{k+1}-\sqrt{k}\le\frac1{2\sqrt{k}}\tag{2} $$ Summing $(2)$ yields $$ \sum_{k=2}^n\frac1{2\sqrt{k}}\le\sqrt{n}-1\le\sum_{k=1}^{n-1}\frac1{2\sqrt{k}}\tag{3} $$ which implies $$ \sqrt{n}-1+\frac1{2\sqrt{n}}\le\sum_{k=1}^n\frac1{2\sqrt{k}}\le\sqrt{n}-\frac12\tag{4} $$ Therefore, $$ 2\sqrt{n}-2+\frac1{\sqrt{n}}\le\sum_{k=1}^n\frac1{\sqrt{k}}\le2\sqrt{n}-1\tag{5} $$ Combining $(5)$ and $$ \sqrt{n}\le\sqrt{n}+\left(n^{1/4}-n^{-1/4}\right)^2=2\sqrt{n}-2+\frac1{\sqrt{n}}\tag{6} $$ yields $$ \sqrt{n}\le\sum_{k=1}^n\frac1{\sqrt{k}}\le2\sqrt{n}-1\tag{7} $$

robjohn
  • 345,667
  • Please clarify item 3 – mohd Sep 22 '14 at 21:37
  • Note that $$2\sqrt{k}\le\sqrt{k+1}+\sqrt{k}\le2\sqrt{k+1}$$ Take the reciprocal of this inequality and apply $(1)$. This gives $(2)$. $(3)$ is just the sum of $(2)$ from $k=1$ to $k=n-1$. – robjohn Sep 22 '14 at 21:40
  • Please clarify the transition to the item3 with step by step – mohd Sep 22 '14 at 21:48
  • Which part is giving you trouble, the sum of the left part, the middle part, or the right part? – robjohn Sep 22 '14 at 22:03
  • the middle part – mohd Sep 22 '14 at 22:07
  • This is a telescoping series. $$\begin{align}\sum_{k=1}^{n-1}(\sqrt{k+1}-\sqrt{k}) &=\sum_{k=1}^{n-1}\sqrt{k+1}-\sum_{k=1}^{n-1}\sqrt{k}\ &=\sum_{k=2}^n\sqrt{k}-\sum_{k=1}^{n-1}\sqrt{k}\ &=\left(\sqrt{n}+\sum_{k=2}^{n-1}\sqrt{k}\right) -\left(\sqrt{1}+\sum_{k=2}^{n-1}\sqrt{k}\right)\ &=\sqrt{n}-\sqrt{1}\end{align}$$ – robjohn Sep 22 '14 at 22:30
1

In answering a similar question I proved that:

$$\frac{2}{3}N\sqrt{N}\leq\sum_{n=1}^{N}\sqrt{n}\leq\frac{4N+3}{6}\sqrt{N}.$$

This can be achieved through induction, partial summation or a Riemann sums+convexity argument. For this problem, let's try the third way. $f(x)=\frac{1}{\sqrt{x}}$ is a convex function over $[1,N]$, hence the trapezoidal rule overestimates the integral $\int_{1}^{N}\frac{dx}{\sqrt{x}}$: $$\sum_{n=1}^{N}\frac{1}{\sqrt{n}}-\frac{1}{2}\left(\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{N}}\right)\geq 2\sqrt{N}-2,$$ that is just: $$\sum_{n=1}^{N}\frac{1}{\sqrt{n}}\geq 2\sqrt{N}-\frac{3}{2}+\frac{1}{2\sqrt{N}}\tag{1},$$ while the fact that $f(x)$ is decreasing gives: $$\sum_{n=1}^{N}\frac{1}{\sqrt{n}}\leq 1+\int_{1}^{N}\frac{dx}{\sqrt{x}}=2\sqrt{N}-1,\tag{2}$$ establishing the following tight inequality:

$$2\sqrt{N}-\frac{3}{2}\leq \sum_{n=1}^{N}\frac{1}{\sqrt{n}}\leq 2\sqrt{N}-1.$$

Community
  • 1
Jack D'Aurizio
  • 353,855
  • Just to be clear, this proof does not rely on induction as the perfectly fine answer of Eupraxis1981 does. It is written just to show an efficient technique for bounding certain sums. – Jack D'Aurizio Aug 13 '14 at 21:27