# 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{matrix} 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{matrix}$

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! > 24, i.e. 24 > 16. Now suppose it's true for n = k, k ≥ 4, i.e.

k! > 2k

it follows that

(k+1)k! > (k+1)2k > 2k+1
(k+1)! > 2k+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)^2n^2}{4}$


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

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

it follows that

$\begin{matrix} 1^3 + 2^3 + ...+ k^3 + (k+1)^3 & = &\frac {(k+1)^2k^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{matrix}$

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.

## 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\cdot2+3\cdot2^2+4\cdot2^3+...+n\cdot2^{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\cdot2}+\frac{1}{2\cdot3}+\frac{1}{3\cdot4}+...+\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 divisible 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\times2$

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\cdot2+3\cdot2^2+4\cdot2^3+...+n\cdot2^{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\cdot2+3\cdot2^2+4\cdot2^3+...+k\cdot2^{k-1}=1+(k-1)2^k$

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

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

$1+2\cdot2+3\cdot2^2+4\cdot2^3+...+k\cdot2^{k-1}+(k+1)\cdot2^{k}=1+(k-1)2^k+(k+1)\cdot2^{k}=1+(k+1+k-1)\cdot2^{k}=1+(2k)\cdot2^{k}=1+k\cdot2^{k+1}$
$1+2\cdot2+3\cdot2^2+4\cdot2^3+...+k\cdot2^{k-1}+(k+1)\cdot2^{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{matrix} 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{matrix}$

$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\cdot2}+\frac{1}{2\cdot3}+\frac{1}{3\cdot4}+...+\frac{1}{n\cdot (n+1)}=\frac{n}{n+1}$

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

$\frac{1}{1\cdot2}=\frac{1}{1+1}$

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

$\frac{1}{1\cdot2}+\frac{1}{2\cdot3}+\frac{1}{3\cdot4}+...+\frac{1}{k\cdot (k+1)}=\frac{k}{k+1}$

We aim to show that $\frac{1}{1\cdot2}+\frac{1}{2\cdot3}+\frac{1}{3\cdot4}+...+\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\cdot2}+\frac{1}{2\cdot3}+\frac{1}{3\cdot4}+...+\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{matrix} \frac{1}{1\cdot2}+\frac{1}{2\cdot3}+\frac{1}{3\cdot4}+...+\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{matrix}$

$\frac{1}{1\cdot2}+\frac{1}{2\cdot3}+\frac{1}{3\cdot4}+...+\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{matrix} 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{matrix}$

$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{matrix} (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{matrix}$

$(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{matrix} 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{matrix}$

$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{matrix} (1+x)^{k+1} &\ge& (1+kx) \cdot (1+x) \\ \ &=& 1+kx+x+kx^2 \\ \ &=& 1+(k+1)x+kx^2 \\ \ &\ge& 1+(k+1)x \end{matrix}$

The last step relies on the fact that $kx^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 \Leftrightarrow \frac{1}{4}(k^4+4k^3)<\frac{1}{4}(k^4+4k^3+6k^2+4k+1) \Leftrightarrow 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{matrix} \frac{1}{4}(k+1)^4<\frac{1}{4}k^4+(k+1)^3 &\Leftrightarrow & \frac{1}{4}(k^4+4k^3+6k^2+4k+1)<\frac{1}{4}(k^4+4(k^3+3k^2+3k+1)) \\ \ & \Leftrightarrow & \frac{1}{4}(k^4+4k^3+6k^2+4k+1)<\frac{1}{4}(k^4+4k^3+12k^2+12k+4) \\ \ & \Leftrightarrow & 0 < \frac{1}{4}(6k^2+8k+3) \end{matrix}$

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

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{matrix} \ 2\sqrt{k}+\frac{1}{\sqrt{k+1}}-1 \le 2\sqrt{k+1}-1 &\Leftrightarrow & 2\sqrt{k}+\frac{1}{\sqrt{k+1}} \le 2\sqrt{k+1} \\ \ & \Leftrightarrow & 2\sqrt{k \cdot (k+1)}+1 \le 2(k+1) \\ \ & \Leftrightarrow & 2\sqrt{k \cdot (k+1)} \le 2k+1 \\ \ & \Leftrightarrow & 2^2 \cdot {\sqrt{k \cdot (k+1)}}^2 \le {(2k+1)}^2 \\ \ & \Leftrightarrow & 4k^2 + 4k \le 4k^2 + 4k + 1 \\ \ & \Leftrightarrow & 0 \le 1 \end{matrix}$

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