Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: Mar 27, 2024

Mathematical Induction

Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

Introduction

Mathematical Induction is a methodology for proving natural-number conclusions, a formula or existing theorems.

There are 2 steps involved in order to prove these statements using Induction:

Step 1(Base step) : 
Consider a starting point for the assertion to be true. It will always be true must prove that the statement is correct when n = starting value.

Mathematically

Let n0 be a fixed integer. Suppose T (n) is a statement involving the natural number n, and we wish to prove that P (n) is valid for all n ≥ n0.

T (n0) is true i.e. T (n) is true for n = n0.

Step 2(Induction Step) :
Assuming the statement to be true for any value of n = k. Then prove that the  statement is true for n = k+1.

Mathematically
Let n0 be a fixed integer. Suppose T (n) is a statement involving the natural number n and we wish to prove that P (n) is true for all N ≥ n0.

Assume that the P (k) is true for n = k.

Then P (K+1) should also be true.

Examples

  1. Use the Principle of Mathematical Induction to verify that, for n any positive integer, 6n-1 is divisible by 5.

Solution: 
For any n ≥ 1, let Pn be the statement that 6n − 1 is divisible by 5.
Base Case: The statement P1 says that 
6 1 − 1 = 6 − 1 = 5 Eq No. 1
is divisible by 5, which is true. 
Inductive Step: Fix k ≥ 1, and suppose that Pk holds, that is, 6k − 1 is divisible by 5. 

It remains to show that Pk+1 holds, that is, that 6k+1 − 1 is divisible by 5. 

6 k+1 − 1  = 6(6k ) − 1 
  = 6(6k − 1) − 1 + 6 From Eq. No-1

   = 6(6k − 1) + 5

By Pk, the first term 6(6k − 1) is divisible by 5, the second term is divisible by 5. 

Therefore the left-hand side is also divisible by 5. 

Therefore Pk+1 holds.

Thus, P(n) holds true by the principle of mathematical Induction, for all n ≥ 1.


2.  Verify the following mathematical equation using Mathematical Induction:
1 + 3 + 5 + ··· + 2n − 1 = n2 
Solution: 

Base Step:  We are going to prove P(1). 
LHS of P(1) = 1 
= 12
= RHS of P(1).
So P(1) is true.
Inductive Step: Now, we’ll prove that for any natural number k, “if P(k) is true then P(k +1) is true.” So assume P(k) is true, i.e.
1+3+5+ ··· + 2k − 1 = k2
Therefore for P(k + 1): 
LHS of P(k + 1) = 1 + 3 + 5 + ··· + 2k − 1 + 2(k + 1) − 1
    = (LHS of P(k)) + 2(k + 1) − 1
    = (RHS of P(k)) + 2k + 1 (by inductive assumption)
      = k+ 2k +1
    = (k + 1)2 

    = RHS of P(k + 1)

So P(k + 1) is true, if P(k) is true.

Hence, by induction P(n) is true for all natural numbers

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

FAQs

  1. What do mean by Strong Induction?
    Strong Induction is a different form of mathematical induction. Through this, 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 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.
     
  2. What are some of the practical applications of Mathematical Induction?
    It's a great tool for recursively developing algorithms. If we can discover the answer to n using the attributes of n-1, we can construct a recursive method to compute n by n-1.

 

 

Key Takeaways

In this article we have discussed the ‘Mathematical Induction’, Problem Solving Steps with a few examples. Check out the playlist Basic Mathematics for further topics.

We hope that this blog has helped you enhance your knowledge regarding Mathematical Induction and if you would like to learn more, check out our articles on Library for more articles like this. 

Do upvote our blog to help other ninjas grow. Happy Coding!

Topics covered
1.
Introduction
2.
Examples
3.
FAQs
4.
Key Takeaways