Algebra/Proofs/Exercises

From Wikibooks, the open-content textbooks collection

Current revision (unreviewed)

A Wikibookian suggests that this book or chapter be merged into Mathematical Proof because:
The page Algebra/Proofs was merged there but this exercise page became orphaned
Please discuss whether or not this merge should happen on the discussion page.

[edit] Proof exercises

 1. Show that the identity:
 
 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! > 2ⁿ 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:

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.

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 2 n - 48 n - 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$

[edit] Solutions for "More on Induction"

[edit] 1.

[edit] i)

$2 + 4 + 6 + ... + 2 k = 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 + ... + 2 k = k (k + 1)

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

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

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

2 + 4 + 6 + ... + 2 k + 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}$ .

[edit] 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 = 3 k + 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}$ .

[edit] 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 = 5 k + 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}$ .

[edit] 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}$ .

[edit] 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}$ .

[edit] 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.

[edit] 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.

[edit] 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}$ .

[edit] 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.

[edit] 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}$ .

Algebra/Proofs/Exercises

From Wikibooks, the open-content textbooks collection

Contents

[edit] Proof exercises

[edit] More on induction

[edit] Solutions for "More on Induction"

[edit] 1.

[edit] i)

[edit] ii)

[edit] iii)

[edit] iv)

[edit] v)

[edit] vi)

[edit] vii)

[edit] viii)

[edit] ix)

[edit] 2.

Views

Personal tools

Navigation

Search

community

Print/export

Toolbox