Induction

Chapter 2

Proof

Submitted by:

Manolo Cruz Bolito

Chapter2 Mathematical Induction

OBJECTIVES:

• In this section you will be able to apply the procedure for proof by mathematical induction and construct proofs by Principle of Mathematical Induction.

Mathematical Induction

In this section we examine propositions concerning positive integers. The positive integers 1, 2, 3, 4,…are called natural numbers or counting numbers. In this section lower case letters represent natural numbers.

Principle of Mathematical Induction

Mathematical induction is a powerful tool used to prove propositions concerning natural numbers.

Principle of Mathematical Induction

For each natural number n, let [pic] be a proposition about n. If [pic] satisfies:

1) [pic] is true

2) For an arbitrary [pic], [pic] is true implies [pic] is true

Then for all natural numbers,[pic], we have [pic] is true.

Parts 1) and 2) suggest that

[pic]

This is sometimes called the domino effect. Once one of the dominos topples it causes the rest to topple as well.

[pic]

Fig 1 Domino Effect

The process is that we show [pic] is true and by assuming [pic] is true we prove [pic] is true. If both [pic] is true and [pic] implies [pic] then proposition[pic] is true for all natural numbers n.

We can apply this principle of mathematical induction to prove results about natural numbers.

Examples

Example 1

For every natural number n prove the proposition [pic] given by

[pic]

Comment

What does this proposition mean?

It means that if we add the first [pic] natural numbers then the answer will be [pic]. For example if we add the first 2 numbers we have

[pic] [Substituting [pic]into the above]

Similarly we have

[pic]

and so on. We need to show this result for all the natural numbers [pic]. How?

Employ...