5th task: mathematical Induction I & II

16:56 |

TAF3023:DISCRETE MATHEMATICS
Task : Mathematical Induction I & II

1) What do you show in the basis step and what do you show in the inductive step when
you use (ordinary) mathematical induction to prove that a property involving an
integer n is true for all integers greater than or equal to some initial integer?
- You may use example of problems to explain this answer.

2) What is the inductive hypothesis in a proof by (ordinary) mathematical induction?

3) Are you able to use (ordinary) mathematical induction to construct proofs involving
various kinds of statements such as formulas, divisibility properties and inequalities?
- You may use example of problems to explain this answer. Give examples of
question for each type of problems (formulas, divisibility properties and inequalities)
..............................................................................................................................................................

1. For our formula example, our proposition P(n) is . Substituting this definition of P into the outline , we get the following outline for our specific claim :

Proof : We will show that for any positive integer n, using induction on n.

Base : We need to show that the formula for n = 1, i.e. .

Induction : Suppose that for n = 1, 2, …, k-1. We need to show that

^k.

By the deﬁnition of summation notation,

Our inductive hypothesis states that at n = k – 1,

Combining these two formulas, we get that

But

So, combining these equations, we get that ^k which

is what we needed to show.

One way to think of a proof by induction is that it’s a template for

building direct proofs. If I give you the speciﬁc value n = 47, you could

write a direct proof by starting with the base case and using the inductive

step 46 times to work your way from the n = 1 case up to the n = 47 case.

2. PROOFS FOR INEQUALITIES IN MATHEMATHICAL INDUCTION PROBLEM

Let us denote the proposition in question by P (n), where n is a positive integer. The proof involves two steps:

Step 1: We first establish that the proposition P (n) is true for the lowest possible value of the positive integer n.

Step 2: We assume that P (k) is true and establish that P (k+1) is also true

Problem 1:

Use mathematical induction to prove that

1 + 2 + 3 + ... + n = n (n + 1) / 2

for all positive integers n.

Solution to Problem 1:

Let the statement P (n) be

1 + 2 + 3 + ... + n = n (n + 1) / 2
STEP 1: We first show that p (1) is true.

Left Side = 1

Right Side = 1 (1 + 1) / 2 = 1
Both sides of the statement are equal hence p (1) is true.
STEP 2: We now assume that p (k) is true

1 + 2 + 3 + ... + k = k (k + 1) / 2
and show that p (k + 1) is true by adding k + 1 to both sides of the above statement

1 + 2 + 3 + ... + k + (k + 1) = k (k + 1) / 2 + (k + 1)

= (k + 1)(k / 2 + 1)

= (k + 1)(k + 2) / 2
The last statement may be written as

1 + 2 + 3 + ... + k + (k + 1) = (k + 1)(k + 2) / 2
Which is the statement p(k + 1).

Problem 2:

Prove that

1² + 2² + 3² + ... + n² = n (n + 1) (2n + 1)/ 6

For all positive integers n.

Solution to Problem 2:

Statement P (n) is defined by

1² + 2² + 3² + ... + n² = n (n + 1) (2n + 1)/ 2
STEP 1: We first show that p (1) is true.

Left Side = 1² = 1

Right Side = 1 (1 + 1) (2*1 + 1)/ 6 = 1
Both sides of the statement are equal hence p (1) is true.
STEP 2: We now assume that p (k) is true

1² + 2² + 3² + ... + k² = k (k + 1) (2k + 1)/ 6
and show that p (k + 1) is true by adding (k + 1)² to both sides of the above statement

1² + 2² + 3² + ... + k² + (k + 1)² = k (k + 1) (2k + 1)/ 6 + (k + 1)²
Set common denominator and factor k + 1 on the right side

= (k + 1) [ k (2k + 1)+ 6 (k + 1) ] /6
Expand k (2k + 1)+ 6 (k + 1)

= (k + 1) [ 2k² + 7k + 6 ] /6
Now factor 2k² + 7k + 6.

= (k + 1) [ (k + 2) (2k + 3) ] /6
We have started from the statement P(k) and have shown that

1² + 2² + 3² + ... + k² + (k + 1)² = (k + 1) [ (k + 2) (2k + 3) ] /6
Which is the statement P(k + 1).