MATHEMATICAL INDUCTION

Mr. Chandavale V. V.

Asst Prof .

Department of Mathematics

Raje Ramrao Mahavidyalaya, Jath

1

What is induction?

• A method of proof

​

• It does not generate answers: it only can prove them

​

• Three parts:
• Base case(s): show it is true �for one element
• Inductive hypothesis: assume �it is true for any given element
• Must be clearly labeled!!!
• Show that if it true for the next �highest element

2

Induction example

• Show that the sum of the first n odd integers is n²
• Example: If n = 5, 1+3+5+7+9 = 25 = 5²
• Formally, Show

​

• Base case: Show that P(1) is true

​

3

Induction example, continued

• Inductive hypothesis: assume true for k
• Thus, we assume that P(k) is true, or that

​

​

• Note: we don’t yet know if this is true or not!

​

• Inductive step: show true for k+1
• We want to show that:

4

Induction example, continued

• Recall the inductive hypothesis:

​

• Proof of inductive step:

5

What did we show

• Base case: P(1)
• If P(k) was true, then P(k+1) is true
• i.e., P(k) → P(k+1)

​

• We know it’s true for P(1)
• Because of P(k) → P(k+1), if it’s true for P(1), then it’s true for P(2)
• Because of P(k) → P(k+1), if it’s true for P(2), then it’s true for P(3)
• Because of P(k) → P(k+1), if it’s true for P(3), then it’s true for P(4)
• Because of P(k) → P(k+1), if it’s true for P(4), then it’s true for P(5)
• And onwards to infinity

​

• Thus, it is true for all possible values of n

​

• In other words, we showed that:

6

The idea behind inductive proofs

• Show the base case
• Show the inductive hypothesis
• Manipulate the inductive step so that you can substitute in part of the inductive hypothesis
• Show the inductive step

7

Second induction example

• Rosen, section 3.3, question 2:
• Show the sum of the first n positive even integers is n² + n
• Rephrased:

​

• The three parts:
• Base case
• Inductive hypothesis
• Inductive step

8

Second induction example, continued

• Base case: Show P(1):

​

​

• Inductive hypothesis: Assume

​

​

• Inductive step: Show

9

Second induction example, continued

• Recall our inductive �hypothesis:

​

10

Notes on proofs by induction

• We manipulate the k+1 case to make part of it look like the k case
• We then replace that part with the other side of the k case

11

Third induction example

• Rosen, question 7: Show

​

• Base case: n = 1

​

​

​

• Inductive hypothesis: assume

12

Third induction example

• Inductive step: show

13

Third induction again: what if your inductive hypothesis was wrong?

• Show:

​

• Base case: n = 1:

​

​

​

• But let’s continue anyway…
• Inductive hypothesis: assume

14

Third induction again: what if your inductive hypothesis was wrong?

• Inductive step: show

15

Fourth induction example

• Rosen, question 14: show that n! < nⁿ for all n > 1

​

• Base case: n = 2

2! < 2²

2 < 4

• Inductive hypothesis: assume k! < k^k
• Inductive step: show that (k+1)! < (k+1)^k+1

16

Strong induction

• Weak mathematical induction assumes P(k) is true, and uses that (and only that!) to show P(k+1) is true

​

• Strong mathematical induction assumes P(1), P(2), …, P(k) are all true, and uses that to show that P(k+1) is true.

17

Strong induction example 1

• Show that any number > 1 can be written as the product of primes

​

• Base case: P(2)
• 2 is the product of 2 (remember that 1 is not prime!)
• Inductive hypothesis: P(1), P(2), P(3), …, P(k) are all true
• Inductive step: Show that P(k+1) is true

18

Strong induction example 1

• Inductive step: Show that P(k+1) is true
• There are two cases:
• k+1 is prime
• It can then be written as the product of k+1
• k+1 is composite
• It can be written as the product of two composites, a and b, where 2 ≤ a ≤ b < k+1
• By the inductive hypothesis, both P(a) and P(b) are true

19

Strong induction vs. non-strong induction

• Rosen, question 31: Determine which amounts of postage can be written with 5 and 6 cent stamps

​

• Prove using both versions of induction

​

• Similar to example 15 (page 250)

​

• Answer: any postage ≥ 20

20

Answer via mathematical induction

• Show base case: P(20):
• 20 = 5 + 5 + 5 + 5
• Inductive hypothesis: Assume P(k) is true
• Inductive step: Show that P(k+1) is true
• If P(k) uses a 5 cent stamp, replace that stamp with a 6 cent stamp
• If P(k) does not use a 5 cent stamp, it must use only 6 cent stamps
• Since k > 18, there must be four 6 cent stamps
• Replace these with five 5 cent stamps to obtain k+1

21

Answer via strong induction

• Show base cases: P(20), P(21), P(22), P(23), and P(24)
• 20 = 5 + 5 + 5 + 5
• 21 = 5 + 5 + 5 + 6
• 22 = 5 + 5 + 6 + 6
• 23 = 5 + 6 + 6 + 6
• 24 = 6 + 6 + 6 + 6
• Inductive hypothesis: Assume P(20), P(21), …, P(k) are all true
• Inductive step: Show that P(k+1) is true
• We will obtain P(k+1) by adding a 5 cent stamp to P(k+1-5)
• Since we know P(k+1-5) = P(k-4) is true, our proof is complete

22

Strong induction vs. non-strong induction, take 2

• Rosen, section 3.4, example 15: Show that every postage amount 12 cents or more can be formed using only 4 and 5 cent stamps

​

• Similar to the previous example

23

Answer via mathematical induction

• Show base case: P(12):
• 12 = 4 + 4 + 4
• Inductive hypothesis: Assume P(k) is true
• Inductive step: Show that P(k+1) is true
• If P(k) uses a 4 cent stamp, replace that stamp with a 5 cent stamp to obtain P(k+1)
• If P(k) does not use a 4 cent stamp, it must use only 5 cent stamps
• Since k > 10, there must be at least three 5 cent stamps
• Replace these with four 4 cent stamps to obtain k+1
• Note that only P(k) was assumed to be true

24

Answer via strong induction

• Show base cases: P(12), P(13), P(14), and P(15)
• 12 = 4 + 4 + 4
• 13 = 4 + 4 + 5
• 14 = 4 + 5 + 5
• 15 = 5 + 5 + 5
• Inductive hypothesis: Assume P(12), P(13), …, P(k) are all true
• For k ≥ 15
• Inductive step: Show that P(k+1) is true
• We will obtain P(k+1) by adding a 4 cent stamp to P(k+1-4)
• Since we know P(k+1-4) = P(k-3) is true, our proof is complete
• Note that P(12), P(13), …, P(k) were all assumed to be true

25

​

​

​

THANK YOU

26