Algebra/Proofs/Exercises

Proof exercises

 1. Show that the identity:
 $1+2+3+...+n=\frac{n(n+1)}{2}$
 holds for all positive integers.

First, we show that it holds for integers 1, 2 and 3

1 = 2×1/2

1 + 2 = 3×2/2

1 + 2 + 3 = 4×3/2 = 6

Suppose the identiy holds for some number k, then

$1+2+3+...+k=\frac{1}{2}(k+1)k$

is true.

We aim to show that:

$1+2+3+...+k+(k+1)=\frac{1}{2}(k+2)(k+1)$

is also true. We proceed

$\begin{array}{cccc}1+2+3+...+k& & =& \frac{1}{2}(k+1)k\\ \\ 1+2+3+...+k& +(k+1)& =& \frac{1}{2}(k+1)k+(k+1)\\ \\ & & =& (k+1)(\frac{k}{2}+1)\\ \\ & & =& \frac{1}{2}(k+1)(k+2)\end{array}$

which is what we have set out to show. Since the identity holds for 3, it also holds for 4 and since it holds for 4 it also holds for 5, and 6 and 7 and so on.

 2. Show that n! > 2n for n ≥ 4.

The claim is true for n = 4. As 4! > 2⁴, i.e. 24 > 16. Now suppose it's true for n = k, k ≥ 4, i.e.

k! > 2^k

it follows that

(k+1)k! > (k+1)2^k > 2^k+1

(k+1)! > 2^k+1

We have shown that if for n = k then it's also true for n = k + 1. Since it's true for n = 4, it's true for n = 5, 6, 7, 8 and so on for all n.

 3. Show that:
 $1^3+2^3+...+n^3=\frac{(n+1{)}^2{n}^2}{4}$

Suppose it's true for n = k, i.e.

$1^3+2^3+...+k^3=\frac{(k+1{)}^2{k}^2}{4}$

it follows that

$\begin{array}{ccc}{1}^3+2^3+...+k^3+(k+1{)}^3& =& \frac{(k+1{)}^2{k}^2}{4}+(k+1{)}^3\\ & =& (k+1{)}^2(\frac{k^2}{4}+(k+1))\\ & =& \frac{1}{4}(k+1{)}^2(k^2+4k+4)\\ & =& \frac{1}{4}(k+1{)}^2(k+2{)}^2\end{array}$

We have shown that if it's true for n = k then it's also true for n = k + 1. Now it's true for n = 1 (clear). Therefore it's true for all integers.

Next Page

More on induction

1. Prove by induction that the given formula is true for every positive integer n.

i) $2+4+6+...+2n=\frac{}{}n(n+1)$

ii) $1+4+7+...+(3n-2)=\frac{1}{2}n(3n-1)$

iii) $2+7+12+...+(5n-3)=\frac{1}{2}n(5n-1)$

iv) $1+2\cdot 2+3\cdot 2^2+4\cdot 2^3+...+n\cdot 2^{n-1}=1+(n-1)2^n$

v) $1^2+2^2+3^2+...+n^2=\frac{1}{6}n(n+1)(2n+1)$

vi) $\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{3\cdot 4}+...+\frac{1}{n\cdot (n+1)}=\frac{n}{n+1}$

vii) $3+3^2+3^3+...+3^n=\frac{3}{2}(3^n-1)$

viii) $(1+2^5+...+n^5)+(1+2^7+...+n^7)=2{\left[\frac{n(n+1)}{2}\right]}^4$

ix) $1+r+r^2+...+r^{n-1}=\frac{1-r^n}{1-r}$

2. Prove that the following inequalities hold for all $n\in \mathbb{N}$

i) $(1+x{)}^n\ge 1+nx$ if $x\ge -1$ (the so called Bernoulli's inequality)

ii) $1^3+2^3+...+(n-1{)}^3<\frac{1}{4}{n}^4<1^3+2^3+...+n^3$

iii) $1+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+...+\frac{1}{\sqrt{n}}\le 2\sqrt{n}-1$ (Hard)

3. Prove by induction that the following statements are true for every positive integer n

i) 3 is a factor of $n^3-n+3$

ii) 9 is a factor of $10^{n+1}+3\cdot 10^n+5$

iii) 4 is a factor of $5^n-1$

iv) $x-y$ is a factor of $x^n-y^n$

v) $7^{2n}-48n-1$ is dividible by 2304

4. In each case find $n_0\in \mathbb{N}$ such that the inequality holds for all $n\ge n_0$, and give a proof by induction.

i) $n!>2^n$

Solutions for "More on Induction"

1.

i)

$2+4+6+...+2k=k(k+1)$

First, we show that this statement holds for n=1.

$2=1\times 2$

Assume that the equation holds for n=k. Then,

$2+4+6+...+2k=k(k+1)$

We aim to show that $2+4+6+...+2k+2(k+1)=(k+1)(k+2)$.

Adding $2(k+1)$ to both sides,

$2+4+6+...+2k+2(k+1)=k(k+1)+2(k+1)$

$2+4+6+...+2k+2(k+1)=(k+1)(k+2)$,

which is what we set out to prove. By mathematical induction, the formula holds for all $n\in \mathbb{N}$.

ii)

$1+4+7+...+(3n-2)=\frac{1}{2}n(3n-1)$

First, we show that this statement holds for n=1.

$1=\frac{1}{2}\times 1(3-1)=1$

Assume that the equation holds for n=k. Then,

$1+4+7+...+(3k-2)=\frac{1}{2}k(3k-1)$

We aim to show that $1+4+7+...+(3k-2)+(3k+1)=\frac{1}{2}(k+1)(3k+2)$.

Adding $3(k+1)-2=3k+1$ to both sides,

$1+4+7+...+(3k-2)+(3k+1)=\frac{1}{2}k(3k-1)+(3k+1)$

$1+4+7+...+(3k-2)+(3k+1)=\frac{1}{2}(3k^2-k+6k+2)=\frac{1}{2}(3k^2+5k+2)=\frac{1}{2}(k+1)(3k+2)$

$1+4+7+...+(3k-2)+(3k+1)=\frac{1}{2}(k+1)(3k+2)$,

which is what we set out to prove. By mathematical induction, the formula holds for all $n\in \mathbb{N}$.

iii)

$2+7+12+...+(5n-3)=\frac{1}{2}n(5n-1)$

First, we show that this statement holds for n=1.

$2=\frac{1}{2}\times 1(5-1)=2$

Assume that the equation holds for n=k. Then,

$2+7+12+...+(5k-3)=\frac{1}{2}k(5k-1)$

We aim to show that $2+7+12+...+(5k-3)+(5(k+1)-3)=\frac{1}{2}(k+1)(5(k+1)-1)$, same as $2+7+12+...+(5k-3)+(5k+2)=\frac{1}{2}(k+1)(5k+4)$.

Adding $5(k+1)-3=5k+2$ to both sides,

$2+7+12+...+(5k-3)+(5k+2)=\frac{1}{2}k(5k-1)+(5k+2)$

$2+7+12+...+(5k-3)+(5k+2)=\frac{1}{2}(5k^2-k+10k+4)=\frac{1}{2}(5k^2+9k+4)=\frac{1}{2}(k+1)(5k+4)$

$2+7+12+...+(5k-3)+(5k+2)=\frac{1}{2}(k+1)(5k+4)$,

which is what we set out to prove. By mathematical induction, the formula holds for all $n\in \mathbb{N}$.

iv)

$1+2\cdot 2+3\cdot 2^2+4\cdot 2^3+...+n\cdot 2^{n-1}=1+(n-1)2^n$

First, we show that this statement holds for n=1.

$1=1+(1-1)2^1=1$

Assume that the equation holds for n=k. Then,

$1+2\cdot 2+3\cdot 2^2+4\cdot 2^3+...+k\cdot 2^{k-1}=1+(k-1)2^k$

We aim to show that $1+2\cdot 2+3\cdot 2^2+4\cdot 2^3+...+k\cdot 2^{k-1}+(k+1)\cdot 2^{(k+1)-1}=1+((k+1)-1)2^{(k+1)}$, same as $1+2\cdot 2+3\cdot 2^2+4\cdot 2^3+...+k\cdot 2^{k-1}+(k+1)\cdot 2^k=1+(k)2^{k+1}$.

Adding $(k+1)\cdot 2^{(k+1)-1}=(k+1)\cdot 2^k$ to both sides,

$1+2\cdot 2+3\cdot 2^2+4\cdot 2^3+...+k\cdot 2^{k-1}+(k+1)\cdot 2^k=1+(k-1)2^k+(k+1)\cdot 2^k=1+(k+1+k-1)\cdot 2^k=1+(2k)\cdot 2^k=1+k\cdot 2^{k+1}$

$1+2\cdot 2+3\cdot 2^2+4\cdot 2^3+...+k\cdot 2^{k-1}+(k+1)\cdot 2^k=1+(k)2^{k+1}$,

which is what we set out to prove. By mathematical induction, the formula holds for all $n\in \mathbb{N}$.

v)

$1^2+2^2+3^2+...+n^2=\frac{1}{6}n(n+1)(2n+1)$

First, we show that this statement holds for n=1.

$1^2=\frac{1}{6}1(1+1)(2+1)=1$

Assume that the equation holds for n=k. Then,

$1^2+2^2+3^2+...+k^2=\frac{1}{6}k(k+1)(2k+1)$

We aim to show that $1^2+2^2+3^2+...+k^2+(k+1{)}^2=\frac{1}{6}(k+1)((k+1)+1)(2(k+1)+1)$, same as $1^2+2^2+3^2+...+k^2+(k+1{)}^2=\frac{1}{6}(k+1)(k+2)(2k+3)$.

Adding $(k+1{)}^2$ to both sides,

$\begin{array}{ccc}{1}^2+2^2+3^2+...+k^2+(k+1{)}^2& =& \frac{1}{6}k(k+1)(2k+1)+(k+1{)}^2\\ & =& \frac{1}{6}(k(k+1)(2k+1)+6(k+1{)}^2)\\ & =& \frac{1}{6}((k+1)(k(2k+1)+6(k+1)))\\ & =& \frac{1}{6}((k+1)(2k^2+k+6k+6))\\ & =& \frac{1}{6}((k+1)(2k^2+7k+6))\\ & =& \frac{1}{6}((k+1)(k+2)(2k+3))\end{array}$

$1^2+2^2+3^2+...+k^2+(k+1{)}^2=\frac{1}{6}(k+1)(k+2)(2k+3)$,

which is what we set out to prove. By mathematical induction, the formula holds for all $n\in \mathbb{N}$.

vi)

$\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{3\cdot 4}+...+\frac{1}{n\cdot n+1}=\frac{n}{n+1}$

First, we show that this statement holds for n=1.

$\frac{1}{1\cdot 2}=\frac{1}{1+1}$

Assume that the equation holds for n=k. Then,

$\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{3\cdot 4}+...+\frac{1}{k\cdot (k+1)}=\frac{k}{k+1}$

We aim to show that $\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{3\cdot 4}+...+\frac{1}{k\cdot (k+1)}+\frac{1}{(k+1)\cdot ((k+1)+1)}=\frac{(k+1)}{(k+1)+1}$, same as $\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{3\cdot 4}+...+\frac{1}{k\cdot (k+1)}+\frac{1}{(k+1)\cdot (k+2)}=\frac{k+1}{k+2}$.

Adding $\frac{1}{(k+1)\cdot (k+2)}$ to both sides,

$\begin{array}{ccc}\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{3\cdot 4}+...+\frac{1}{k\cdot (k+1)}+\frac{1}{(k+1)\cdot (k+2)}& =& \frac{k}{k+1}+\frac{1}{(k+1)\cdot (k+2)}\\ & =& \frac{1+(k)(k+2)}{(k+1)\cdot (k+2)}\\ & =& \frac{k^2+2k+1}{(k+1)\cdot (k+2)}\\ & =& \frac{(k+1{)}^2}{(k+1)\cdot (k+2)}\\ & =& \frac{(k+1)}{(k+2)}\end{array}$

$\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{3\cdot 4}+...+\frac{1}{k\cdot (k+1)}+\frac{1}{(k+1)\cdot (k+2)}=\frac{k+1}{k+2}$,

which is what we set out to prove. By mathematical induction, the formula holds for all $n\in \mathbb{N}$.

This problem can be solved without mathematical induction. We note that $\frac{1}{n\cdot n+1}=\frac{1}{n}-\frac{1}{n+1}$. Then, the question can be paraphrased as $\frac{1}{1}-\frac{1}{2}+\frac{1}{2}-\frac{1}{3}+\frac{1}{3}-\frac{1}{4}+...+\frac{1}{n}-\frac{1}{n+1}=\frac{n}{n+1}$, which simplfies to $\frac{1}{1}-\frac{1}{n+1}=\frac{n}{n+1}$, or $\frac{n+1-1}{n+1}=\frac{n}{n+1}$. Q.E.D.

vii)

$3+3^2+3^3+...+3^n=\frac{3}{2}(3^n-1)$

First, we show that this statement holds for n=1.

$3=\frac{3}{2}(3^1-1)=3$

Assume that the equation holds for n=k. Then,

$3+3^2+3^3+...+3^k=\frac{3}{2}(3^k-1)$

We aim to show that $3+3^2+3^3+...+3^k+3^{k+1}=\frac{3}{2}(3^{k+1}-1)$.

Adding $3^{k+1}$ to both sides,

$\begin{array}{ccc}3+3^2+3^3+...+3^k+3^{k+1}& =& \frac{3}{2}(3^k-1)+3^{k+1}\\ & =& \frac{3}{2}(3^k-1+\frac{2}{3}\cdot 3^{k+1})\\ & =& \frac{3}{2}(3^k-1+2\cdot 3^k)\\ & =& \frac{3}{2}(3\cdot 3^k-1)\\ & =& \frac{3}{2}(3^{k+1}-1)\end{array}$

$3+3^2+3^3+...+3^k+3^{k+1}=\frac{3}{2}(3^{k+1}-1)$,

which is what we set out to prove. By mathematical induction, the formula holds for all $n\in \mathbb{N}$.

This can also be proven using the sum formula for a geometric series.

viii)

$(1+2^5+...+n^5)+(1+2^7+...+n^7)=2{\left[\frac{n(n+1)}{2}\right]}^4$

First, we show that this statement holds for n=1.

$1+1=2{\left[\frac{1(1+1)}{2}\right]}^4=2$

Assume that the equation holds for n=k. Then,

$(1+2^5+...+k^5)+(1+2^7+...+k^7)=2{\left[\frac{k(k+1)}{2}\right]}^4$

We aim to show that $(1+2^5+...+k^5+(k+1{)}^5)+(1+2^7+...+k^7+(k+1{)}^7)=2{\left[\frac{(k+1)(k+2)}{2}\right]}^4$.

Adding $(k+1{)}^5+(k+1{)}^7$ to both sides,

$\begin{array}{ccc}(1+2^5+...+k^5+(k+1{)}^5)+(1+2^7+...+k^7+(k+1{)}^7)& =& 2{\left[\frac{k(k+1)}{2}\right]}^4+(k+1{)}^5+(k+1{)}^7\\ & =& \frac{1}{8}{k}^4(k+1{)}^4+(k+1{)}^5+(k+1{)}^7\\ & =& \frac{1}{8}(k+1{)}^4(k^4+8(k+1)+8(k+1{)}^3)\\ & =& \frac{1}{8}(k+1{)}^4(k^4+8k+8+8k^3+24k^2+24k+8)\\ & =& \frac{1}{8}(k+1{)}^4(k^4+8k^3+24k^2+32k+16)\\ & =& \frac{1}{8}(k+1{)}^4(k+2{)}^4\\ & =& 2{\left[\frac{(k+1)(k+2)}{2}\right]}^4\end{array}$

$(1+2^5+...+k^5+(k+1{)}^5)+(1+2^7+...+k^7+(k+1{)}^7)=2{\left[\frac{(k+1)(k+2)}{2}\right]}^4$,

which is what we set out to prove. By mathematical induction, the formula holds for all $n\in \mathbb{N}$.

ix)

$1+r+r^2+...+r^{n-1}=\frac{1-r^n}{1-r}$

First, we show that this statement holds for n=1.

$1=\frac{1-r^1}{1-r}=1$

Assume that the equation holds for n=k. Then,

$1+r+r^2+...+r^{k-1}=\frac{1-r^k}{1-r}$

We aim to show that $1+r+r^2+...+r^{k-1}+r^k=\frac{1-r^{k+1}}{1-r}$.

Adding $r^k$ to both sides,

$\begin{array}{ccc}1+r+r^2+...+r^{k-1}+r^k& =& \frac{1-r^k}{1-r}+r^k\\ & =& \frac{1-r^k+(1-r)r^k}{1-r}\\ & =& \frac{1-r^k+r^k-r^{k+1}}{1-r}\\ & =& \frac{1-r^{k+1}}{1-r}\end{array}$

$1+r+r^2+...+r^{k-1}+r^k=\frac{1-r^{k+1}}{1-r}$,

which is what we set out to prove. By mathematical induction, the formula holds for all $n\in \mathbb{N}$.

This problem can be solved without using mathematical induction.

$1+r+r^2+...+r^{n-1}=\frac{1-r^n}{1-r}$

multiply both sides by $1-r$

$(1+r+r^2+...+r^{n-1})(1-r)=1-r^n$

expand,

$((1-r)+(r-r^2)+(r^2-r^3)...(r^{n-1}-r^n)=1-r^n$

and simplify.

$1-r^n=1-r^n$. Q.E.D.

2.

====i)==== $(1+x{)}^n\ge 1+nx$ if $x\ge -1$

First, we show that this statement holds for n=1.

$(1+x{)}^1\ge 1+1\times x$ because $(1+x{)}^1=1+1\times x$

Assume that the equation holds for n=k. Then,

$(1+x{)}^k\ge 1+kx$

We aim to show that $(1+x{)}^{k+1}\ge 1+(k+1)x$.

Multyplying $(1+x)$ by both sides, (desn't alter the sign of the inequality because $x\ge -1$, and so $x+1\ge 0$)

$\begin{array}{ccc}(1+x{)}^{k+1}& \ge & (1+kx)\cdot (1+x)\\ & =& 1+kx+x+k{x}^2\\ & =& 1+(k+1)x+k{x}^2\\ & \ge & 1+(k+1)x\end{array}$

The last step relies on the fact that $k{x}^2\ge 0$, since $k\ge 0$ and a square is always greater than or equal to 0.

$(1+x{)}^{k+1}\ge 1+(k+1)x$,

which is what we set out to prove. By mathematical induction, the formula holds for all $n\in \mathbb{N}$.

====ii)==== $1^3+2^3+...+(n-1{)}^3<\frac{1}{4}{n}^4<1^3+2^3+...+n^3$

First, we show that this statement holds for n = 1 and n = 2.

$(1-1{)}^3<\frac{1}{4}{1}^4<1^3$ because $0<\frac{1}{4}<1$

$(1-1{)}^3+1^3<\frac{1}{4}{2}^4<1^3+2^3$ because $1<4<9$

Assume that the inequality holds for n=k. Then,

$1^3+2^3+...+(k-1{)}^3<\frac{1}{4}{k}^4<1^3+2^3+...+k^3$

We aim to show that $1^3+2^3+...+k^3<\frac{1}{4}(k+1{)}^4$ and $\frac{1}{4}(k+1{)}^4<1^3+2^3+...+(k+1{)}^3$

We know that $1^3+2^3+...+k^3<\frac{1}{4}{k}^4+k^3$ (added $k^3$ to both sides of $1^3+2^3+...+(k-1{)}^3<\frac{1}{4}{k}^4$).

Now we need to show that $\frac{1}{4}{k}^4+k^3<\frac{1}{4}(k+1{)}^4$

$\frac{1}{4}{k}^4+k^3<\frac{1}{4}(k+1{)}^4\iff \frac{1}{4}(k^4+4k^3)<\frac{1}{4}(k^4+4k^3+6k^2+4k+1)\iff 0<\frac{1}{4}(6k^2+4k+1)$

The last statement is clearly true ($k>0$). Therefore, $\frac{1}{4}{k}^4+k^3<\frac{1}{4}(k+1{)}^4$ and thus $1^3+2^3+...+k^3<\frac{1}{4}{k}^4+k^3<\frac{1}{4}(k+1{)}^4$.

Now we show that $\frac{1}{4}(k+1{)}^4<1^3+2^3+...+(k+1{)}^3$. We know that $\frac{1}{4}{k}^4+(k+1{)}^3<1^3+2^3+...+(k+1{)}^3$ (added $(k+1{)}^3$ to both sides of $\frac{1}{4}{k}^4<1^3+2^3+...+k^3$). Now we need to show that $\frac{1}{4}(k+1{)}^4<\frac{1}{4}{k}^4+(k+1{)}^3$

$\begin{array}{ccc}\frac{1}{4}(k+1{)}^4<\frac{1}{4}{k}^4+(k+1{)}^3& \iff & \frac{1}{4}(k^4+4k^3+6k^2+4k+1)<\frac{1}{4}(k^4+4(k^3+3k^2+3k+1))\\ & \iff & \frac{1}{4}(k^4+4k^3+6k^2+4k+1)<\frac{1}{4}(k^4+4k^3+12k^2+12k+4)\\ & \iff & 0<\frac{1}{4}(6k^2+8k+3)\end{array}$

The last statement is clearly true ($k>0$). Therefore, $\frac{1}{4}(k+1{)}^4<\frac{1}{4}{k}^4+(k+1{)}^3$ and thus $\frac{1}{4}(k+1{)}^4<1^3+2^3+...+(k+1{)}^3$.

Multyplying $(1+x)$ by both sides, (desn't alter the sign of the inequality because $x\ge -1$, and so $x+1\ge 0$) Combining both inequalities we proved, we get the one we needed for the inductive step.

$1^3+2^3+...+k^3<\frac{1}{4}(k+1{)}^4$ and $\frac{1}{4}(k+1{)}^4<1^3+2^3+...+(k+1{)}^3$,

and by mathematical induction, the formula holds for all $n\in \mathbb{N}$.

====iii)==== $1+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+...+\frac{1}{\sqrt{n}}\le 2\sqrt{n}-1$

First, we show that this statement holds for n = 1.

$1\le 2\sqrt{n}-1$ because $1\le 1$

Assume that the inequality holds for n=k. Then,

$1+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+...+\frac{1}{\sqrt{k}}\le 2\sqrt{k}-1$

We aim to show that $1+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+...+\frac{1}{\sqrt{k}}+\frac{1}{\sqrt{k+1}}\le 2\sqrt{k+1}-1$

We know that $1+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+...+\frac{1}{\sqrt{k}}+\frac{1}{\sqrt{k+1}}\le 2\sqrt{k}+\frac{1}{\sqrt{k+1}}-1$ (added $\frac{1}{\sqrt{k+1}}$ to both sides of $1+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+...+\frac{1}{\sqrt{k}}\le 2\sqrt{k}-1$).

Now we need to show that $2\sqrt{k}+\frac{1}{\sqrt{k+1}}-1\le 2\sqrt{k+1}-1$

$\begin{array}{ccc}2\sqrt{k}+\frac{1}{\sqrt{k+1}}-1\le 2\sqrt{k+1}-1& \iff & 2\sqrt{k}+\frac{1}{\sqrt{k+1}}\le 2\sqrt{k+1}\\ & \iff & 2\sqrt{k\cdot (k+1)}+1\le 2(k+1)\\ & \iff & 2\sqrt{k\cdot (k+1)}\le 2k+1\\ & \iff & 2^2\cdot {\sqrt{k\cdot (k+1)}}^2\le {(2k+1)}^2\\ & \iff & 4k^2+4k\le 4k^2+4k+1\\ & \iff & 0\le 1\end{array}$

The last statement is clearly true. Therefore, $2\sqrt{k}+\frac{1}{\sqrt{k+1}}-1\le 2\sqrt{k+1}-1$ and thus $1+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+...+\frac{1}{\sqrt{k}}+\frac{1}{\sqrt{k+1}}\le 2\sqrt{k}+\frac{1}{\sqrt{k+1}}-1\le 2\sqrt{k+1}-1$, the inductive step, and by mathematical induction, the formula holds for all $n\in \mathbb{N}$.

Next Page