Mathematical Induction

Posted By on April 29, 2016


Download PDF
Propositional Logic
Recurrence Relation

Mathematical induction, is a technique for proving results or establishing statements for natural numbers. This part illustrates the method through a variety of examples.

Definition

Mathematical Induction is a mathematical technique which is used to prove a statement, a formula or a theorem is true for every natural number.

The technique involves two steps to prove a statement, as stated below −

Step 1(Base step) − It proves that a statement is true for the initial value.

Step 2(Inductive step) − It proves that if the statement is true for the nth iteration (or number n), then it is also true for (n+1)thiteration ( or number n+1).

How to Do It

Step 1 − Consider an initial value for which the statement is true. It is to be shown that the statement is true for n = initial value.

Step 2 − Assume the statement is true for any value of n = k. Then prove the statement is true for n = k+1. We actually breakn = k+1 into two parts, one part is n = k (which is already proved) and try to prove the other part.

Problem 1

3n−1 is a multiple of 2 for n = 1, 2, …

Solution

Step 1 − For n = 1, 31−1 = 3−1 = 2 which is a multiple of 2

Step 2 − Let us assume 3n−1 is true for n = k, Hence, 3k −1 is true (It is an assumption)

We have to prove that 3k+1−1 is also a multiple of 2

3k+1 − 1 = 3 × 3k − 1 = (2 × 3k) + (3k −1)

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

Hence, 3k+1 − 1 is a multiple of 2.

So, it is proved that 3n − 1 is a multiple of 2.

Problem 2

1 + 3 + 5 + … + (2n−1) = n2 for n = 1, 2, …

Solution

Step 1 − For n = 1, 1 = 12, Hence, step 1 is satisfied.

Step 2 − Let us assume the statement is true for n = k.

Hence, 1 + 3 + 5 + … + (2k−1) = k2 is true (It is an assumption)

We have to prove that 1 + 3 + 5 + … + (2(k+1)−1) = (k+1)2also holds

1 + 3 + 5 + … + (2(k+1) − 1)

= 1 + 3 + 5 + … + (2k+2 − 1)

= 1 + 3 + 5 + … + (2k + 1)

= 1 + 3 + 5 + … + (2k − 1) + (2k + 1)

= k2 + (2k + 1)

= (k + 1)2

So, 1 + 3 + 5 + … + (2(k+1) − 1) = (k+1)2 hold which satisfies the step 2.

Hence, 1 + 3 + 5 + … + (2n − 1) = n2 is proved.

Problem 3

Prove that (ab)n = anbn is true for every natural number n

Solution

Step 1 − For n = 1, (ab)1 = a1b1 = ab, Hence, step 1 is satisfied.

Step 2 − Let us assume the statement is true for n = k, Hence, (ab)k = akbk is true (It is an assumption).

We have to prove that (ab)k+1 = ak+1bk+1 also hold

Given, (ab)k = akbk

Or, (ab)k(ab) = (akbk) (ab) [Multiplying both side by ‘ab’]

Or, (ab)k+1 = (aak) ( bbk)

Or, (ab)k+1 = (ak+1bk+1)

Hence, step 2 is proved.

So, (ab)n = anbn is true for every natural number n.

Strong Induction

Strong Induction is another form of mathematical induction. Through this induction technique, we can prove that a propositional function, P(n) is true for all positive integers, n, using the following steps −

  • Step 1(Base step) − It proves that the initial propositionP(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.
Propositional Logic
Recurrence Relation

Download PDF

Posted by Akash Kurup

Founder and C.E.O, World4Engineers Educationist and Entrepreneur by passion. Orator and blogger by hobby

Website: http://world4engineers.com