# Algebra/Proofs/Exercises

A Wikibookian suggests that this book or chapter be merged into Mathematical Proof because:Please discuss whether or not this merge should happen on the discussion page. |

## Contents

## Proof exercises[edit]

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

is true.

We aim to show that:

is also true. We proceed

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^{n}for n ≥ 4.

The claim is true for n = 4. As 4! > 2^{4}, 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.

it follows that

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

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

i)

ii)

iii)

iv)

v)

vi)

vii)

viii)

ix)

2. Prove that the following inequalities hold for all

i) if (the so called *Bernoulli's inequality*)

ii)

iii) (Hard)

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

i) 3 is a factor of

ii) 9 is a factor of

iii) 4 is a factor of

iv) is a factor of

v) is divisible by 2304

4. In each case find such that the inequality holds for all , and give a proof by induction.

i)

## Solutions for "More on Induction"[edit]

### 1.[edit]

#### i)[edit]

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

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

We aim to show that .

Adding to both sides,

- ,

which is what we set out to prove. By mathematical induction, the formula holds for all .

#### ii)[edit]

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

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

We aim to show that .

Adding to both sides,

- ,

which is what we set out to prove. By mathematical induction, the formula holds for all .

#### iii)[edit]

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

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

We aim to show that , same as .

Adding to both sides,

- ,

which is what we set out to prove. By mathematical induction, the formula holds for all .

#### iv)[edit]

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

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

We aim to show that , same as .

Adding to both sides,

- ,

which is what we set out to prove. By mathematical induction, the formula holds for all .

#### v)[edit]

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

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

We aim to show that , same as .

Adding to both sides,

- ,

which is what we set out to prove. By mathematical induction, the formula holds for all .

#### vi)[edit]

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

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

We aim to show that , same as .

Adding to both sides,

- ,

which is what we set out to prove. By mathematical induction, the formula holds for all .

This problem can be solved without mathematical induction. We note that . Then, the question can be paraphrased as , which simplfies to , or . Q.E.D.

#### vii)[edit]

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

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

We aim to show that .

Adding to both sides,

- ,

which is what we set out to prove. By mathematical induction, the formula holds for all .

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

#### viii)[edit]

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

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

We aim to show that .

Adding to both sides,

- ,

which is what we set out to prove. By mathematical induction, the formula holds for all .

#### ix)[edit]

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

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

We aim to show that .

Adding to both sides,

- ,

which is what we set out to prove. By mathematical induction, the formula holds for all .

This problem can be solved without using mathematical induction.

multiply both sides by

expand,

and simplify.

. Q.E.D.

### 2.[edit]

====i)==== if

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

- because

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

We aim to show that .

Multyplying by both sides, (desn't alter the sign of the inequality because , and so )

The last step relies on the fact that , since and a square is always greater than or equal to 0.

- ,

which is what we set out to prove. By mathematical induction, the formula holds for all .

====ii)====

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

- because
- because

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

We aim to show that and

We know that (added to both sides of ).

Now we need to show that

The last statement is clearly true (). Therefore, and thus .

Now we show that . We know that (added to both sides of ). Now we need to show that

The last statement is clearly true (). Therefore, and thus .

Multyplying by both sides, (desn't alter the sign of the inequality because , and so ) Combining both inequalities we proved, we get the one we needed for the inductive step.

- and ,

and by mathematical induction, the formula holds for all .

====iii)====

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

- because

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

We aim to show that

We know that (added to both sides of ).

Now we need to show that

The last statement is clearly true. Therefore, and thus , the inductive step, and by mathematical induction, the formula holds for all .