Scribd
Upload
31 views4 pages

Mathematical Induction

The document discusses the concept and process of mathematical induction, which is used to prove that a statement is true for all natural numbers. It explains that mathematical induction works by first proving the base case, then assuming the statement is true for an integer k and using that to prove it is true for k+1. Finally, it provides two examples of using mathematical induction to prove statements, including showing that a certain summation is equal to a formula involving n.

Uploaded by

Psalm Leigh Llagas
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
31 views4 pages

Mathematical Induction

The document discusses the concept and process of mathematical induction, which is used to prove that a statement is true for all natural numbers. It explains that mathematical induction works by first proving the base case, then assuming the statement is true for an integer k and using that to prove it is true for k+1. Finally, it provides two examples of using mathematical induction to prove statements, including showing that a certain summation is equal to a formula involving n.

Uploaded by

Psalm Leigh Llagas
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 4

Module in

Discrete Mathematics

SESSION TOPIC : MATHEMATICAL INDUCTION

LEARNING OBJECTIVES

At the end of the session you will:


1. explain the concept of mathematical induction
2. enumerate the steps in mathematical induction
3. prove formula, theorems or statements using mathematical induction

KEY TERMS
theorem mathematical natural number formula
induction
inductive domino effect

CORE CONTENT

Mathematical Induction is a mathematical technique which is used to prove a statement, a


formula or a theorem is true for every natural number.
Mathematical induction works like domino effect.

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 n th iteration (or number n),
then it is also true for (n+1)th iteration ( or number n+1).

How to do mathematical induction


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 break n = k+1 into two parts, one part
is n = k (which is already proved) and try to prove the other part.

Sample 1.
3n−1 is a multiple of 2 for n = 1, 2, ...
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

Sample 2
SELF ASSESSMENT

Try this!
n(3 n−1)
Show using mathematical induction that 1+4+7+…+(3n-2)= for all positive integers
2
n.

n=1 is true
n=k is true
n=k+1 is also true

REFERENCES

https://www.tutorialspoint.com/discrete_mathematics/
discrete_mathematical_induction.htm#:~:text=Definition,true%20for%20every%20natural
%20number.&text=Step%202(Inductive%20step)%20%E2%88%92,or%20number%20n%2B1).

https://www.mathsisfun.com/algebra/mathematical-induction.html
https://www.youtube.com/watch?v=ei_6MmUdEWY

You might also like