** Definition of Induction**

- Mathematical Induction is a method generally used to prove or establish that a given statement is true for all natural numbers.

**More about Induction**

- It is a method to prove a proposition which is valid for infinitely many different values of a variable.

**Example of Induction**

- Mathematical induction can be used to prove that 1 + 3 + 5 + ---- + (2n - 1) = n
^{2}for all positive integers.

Let P_{n}be the statement 1 + 3 + 5 + ---- + (2n - 1) = n^{2}.

P_{1}is true because (2(1) - 1) = 1^{2}.

Assume that P_{k}is true, so that P_{k}: 1 + 3 + 5 + ------ + (2k - 1)

= k^{2}. [The Inductive Hypothesis.]

The next term on the left hand side would be [2(k + 1) - 1] = (2k + 1).

Add (2k + 1) on both sides to P_{k}.]

1 + 3 + 5 + ------ + (2k - 1) + (2k + 1) = k^{2}+ (2k + 1)

= (k + 1)^{2}= P_{k+1}

So, the equation is true for n = k + 1.

Therefore, P_{n}is true for all positive integers, by mathematical induction.

**Solved Example on Induction**

Using mathematical induction to prove that 1 + 5 + 9 + ------ + (4n - 3)

= n(2n - 1) for all positive integers.

Solution:

Step 1:Let P_{n}be the statement 1 + 5 + 9 + ---- + (4n - 3) = n (2n - 1).

Step 2:P_{1}is true because (4(1) - 3) = 1(2(1) - 1) [The Anchor.]

Step 3:Assume that P_{k}is true, so that P_{k}: 1 + 5 + 9 + ---- + (4k - 3)

= k (2k - 1) [The Inductive Hypothesis.]

Step 4:The next term on the left-hand side would be (4(k + 1) - 3).

Step 5:1 + 5 + 9 + ---- + (4k - 3) + (4(k + 1) - 3)

= k (2k - 1) + (4(k + 1) - 3)

Step 6:= 2k^{2}- k + 4k + 1

Step 7:= 2k^{2}+ 3k + 1

Step 8:= (k + 1)^{2}+ k (k + 1)

Step 9:= (k + 1) (2k + 1) [Factor.]

Step 10:= (k + 1) (2(k + 1) - 1)

Step 11:= P_{k+1}

Step 12:So, the equation is true for n = k + 1.

Step 13:Therefore, P_{k}is true for all positive integers, by mathematical induction.

**Related Terms for Induction**

- Deductive Reasoning
- Inductive Reasoning
- Mathematical Induction