Algebra/Proofs/Exercises

From Wikibooks, open books for an open world
Jump to: navigation, search

Proof exercises[edit]

 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.

Next Page

More on induction[edit]

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

1.[edit]

i)[edit]

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

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

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

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

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

\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)[edit]

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

(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)[edit]

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

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

Next Page