Mathematical Induction

BY: JEEVAN JYOTI GIRI

INSTITUTE OF MATHEMATICS

AND APPLICATIONS

1

Mathematical Induction

Mathematical Induction is a proof technique used to establish the truth of an infinite sequence of statements, usually indexed by natural numbers. It consists of two main steps:

• Base Case: Prove that the statement holds for the first value (usually n = 1).
• Inductive Step: Assume the statement holds for some n = k (Inductive Hypothesis) and prove that it holds for n = k+1.

If both steps are satisfied, then by the principle of induction, the statement is true for all natural numbers n.

​

2

Principles of Mathematical Induction

The Principles of Mathematical Induction are:

• Base Case: Verify that the given statement is true for the smallest value (typically n = 1).
• Inductive Hypothesis: Assume that the statement holds for some arbitrary natural number n = k.
• Inductive Step: Use the assumption to prove that the statement holds for n = k+1.

If these steps are satisfied, the statement is true for all natural numbers.

​

3

Example: Sum of Odd Integers

• Proposition: 1 + 3 + … + (2n-1) = n²

for all integers n≥1.

• Proof (by induction):

1) Basis step:

The statement is true for n=1: 1=1² .

2) Inductive step:

Assume the statement is true for some k≥1

(inductive hypothesis) ,

show that it is true for k+1 .

4

Example: Sum of Odd Integers

• Proof (cont.):

The statement is true for k:

1+3+…+(2k-1) = k² (1)

We need to show it for k+1:

1+3+…+(2(k+1)-1) = (k+1)² (2)

Showing (2):

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

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

k²+(2k+1) = (k+1)² .

We proved the basis and inductive steps,

so we conclude that the given statement true.

by (1)

Important theorems proved by mathematical induction

• Theorem 1 (Sum of the first n integers):

For all integers n≥1,

​

​

• Theorem 2 (Sum of a geometric sequence):

For any real number r except 1, and any integer n≥0,

​

​

6

Proving a divisibility property by mathematical induction

• Proposition: For any integer n≥1,

7ⁿ - 2ⁿ is divisible by 5. (P(n))

• Proof (by induction):

1) Basis step:

The statement is true for n=1: (P(1))

7¹ – 2¹ = 7 - 2 = 5 is divisible by 5.

2) Inductive step:

Assume the statement is true for some k≥1 (P(k))

(inductive hypothesis) ;

show that it is true for k+1 . (P(k+1))

​

7

Proving a divisibility property by mathematical induction

• Proof (cont.): We are given that

P(k): 7^k - 2^k is divisible by 5. (1)

Then 7^k - 2^k = 5a for some a∈Z . (by definition) (2)

We need to show:

P(k+1): 7^k+1 - 2^k+1 is divisible by 5. (3)

7^k+1 - 2^k+1 = 7·7^k - 2·2^k = 5·7^k + 2·7^k - 2·2^k

= 5·7^k + 2·(7^k - 2^k) = 5·7^k + 2·5a (by (2))

= 5·(7^k + 2a) which is divisible by 5. (by def.)

Thus, P(n) is true by induction.

​

8

Strong Induction�

Strong Induction is a variation of mathematical induction that assumes the statement is true for all values up to k (instead of just k) to prove it for k+1. This is useful when a problem depends on multiple previous cases rather than just the immediately preceding one.

Steps of Strong Induction:

• Base Case: Show that the statement holds for the smallest value (e.g., n = 1 or n = 2).
• Inductive Hypothesis: Assume the statement is true for all values n= 1, 2, ..., k.
• Inductive Step: Prove that the statement holds for n = k+1 using the assumption that it is true for all previous values.

9

When to use?

When to Use Strong Induction Over Weak Induction:

• Use weak induction when proving P(k+1) only depends on P(k).
• Use strong induction when proving P(k+1) depends on multiple previous values (e.g., P(k),P(k−1),P(k−2), etc.).

​

10

THANK YOU

11