MATHEMATICAL INDUCTION

A proof by mathematical induction that P(n) is true for every positive integer n consists of two steps:

1. BASIS STEP. The proposition P(1) is shown to be true.

2. INDUCTIVE STEP. The implication

P(n) ® P(n+1) is shown to be true for every positive integer n.

When we complete both steps of a proof by mathematical induction, we have proven that P(n) is true for all positive integers n; that is, we have shown that "n P(n) is true.

Expressed as s rule of inference, this proof technique can be stated as

[P(1) Ù "n (P(n) ® P(n+1))]® "n P(n).