Mathematical Induction - Discrete Mathematics

What is Mathematical Induction?

The technique that is used for proving the results or for natural numbers, the statements are established is known as mathematical induction.

Definition of Mathematical Induction

A mathematical technique used for proving a statement, formula or a theorem is true for every natural number is known as Mathematical Induction. A statement can be proved in two steps:

Step 1(Base step) – The statement is proved to be true for the initial value.

Step 2(Inductive step) – The statement is proved to be true for the nth iteration.

How to Do?

Step 1 – An initial value for which the statement is true is considered. It is represented as n = initial value.

Step 2 – It is assumed that the statement is true for any value of n = k. Then the statement is proved true for n = k+1. Here n = k+1 is broken down into two parts, one part is n = k , which is the proved one and the second part is proved.

Problem 1

MIQis a multiple of 2 for n = 1, 2, ...

Solution

Step 1 − For which is a multiple of 2

Step 2 – It is assumed that3n−1 is true for n=k and hence, 3k−1 is true.

It is to be proved that

1 is also a multiple of 2

The first part (2×3k) is a multiple of 2 and the second part (3k−1) is also true as our previous assumption.

Hence,

Hence it is proved that3n–1 is a multiple of 2.

Problem 2

Solution

Step 1 − For , Hence, step 1 is satisfied.

Step 2 – It is assumed that the statement is true for n=k.

Problem 3

For every natural number n, prove thatis true.

Solution

Step 1 − ForHence, step 1 is satisfied.

What is Strong Induction?

One more form of mathematical induction is Strong Induction. This induction proves that a propositional function P(n) is true for all the positive integers , by using the following steps:

  • Step 1(Base step) – Step 1 proves that the initial proposition P(1) true.
  • Step 2(Inductive step) − It proves that the conditional statement [P(1)∧P(2)∧P(3)∧⋯∧P(k)]→P(k+1) is true for positive integers k.

All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Discrete Mathematics Topics