# Mathematical Induction

## Mathematical Induction Synopsis

**Synopsis**

**Top Concepts**

- There are two types of reasoning — deductive and inductive.
- In deduction, given a statement to be proven, often called a conjecture or a theorem, valid deductive steps are derived and a proof may or may not be established.
- Deduction is the application of a general case to a particular case.
- Inductive reasoning depends on working with each case and developing a conjecture by observing the incidence till each and every case is observed.
- ‘Induction’ means the generalization from particular cases or facts.
- Deductive approach is known as the ‘top-down approach’. The given theorem is narrowed down to a specific hypothesis then to observation. Finally the hypothesis is tested with specific data to get the confirmation (or not) of the original theory.
- Inductive reasoning works the other way, moving from specific observations to broader generalizations and theories. Informally, this is known as the ‘bottom up approach’.
- To prove statements or results formulated in terms of n, where n is a positive integer, a principle based on inductive reasoning called the
**Principle of Mathematical Induction**is used. - The Principle of Mathematical Induction or PMI is one such tool which can be used to prove a wide variety of mathematical statements. Each such statement is assumed as P (n) associated with positive integer n, for which the correctness for the case n = 1 is examined. Then assuming the truth of P(k) for some positive integer k, the truth of P (k + 1) is established.
- Let p(n) denote a mathematical statement such that

• p(1) is true i.e. the statement is true for n = 1.

• p(k + 1) is true whenever p(k) is true i.e. if the statement is true for n = k, then the statement is also true for n = k + 1.

Then the statement is true for all natural numbers ‘n’ by the Principle of Mathematical Induction. - PMI is based on Peano’s Axiom.
- PMI is based on a series of well-defined steps so it is necessary to verify all of them.
- PMI can be used to prove the equality, inequality and divisibility of natural numbers.

**Key Formulae**

- Sum of n natural numbers: 1 + 2 + 3 +….+ n =

- Sum of n
^{2}natural numbers: 1^{2}+ 2^{2}+ 3^{2}+………n^{2}= - Sum of odd natural numbers: 1 + 3 + 5 + 7……+ (2n - 1) = n
^{2}

- Steps of PMI

• Denote the given statement in terms of ‘n’ by P(n).

• Check whether the proposition is true for n = 1.

• Assume that the proposition result is true for n = k.

• Using p(k), prove that the proposition is true for p(k + 1). - Rules of Inequalities

• If a < b and b < c then a < c.

• If a < b then a + c < b + c.

• If a < b and c > 0 which means c is positive, then ac < bc.

• If a < b and c < 0 which means c is negative, then ac > bc.

Download complete content for FREE