What is Mathematical induction?

and how to use it properly!

by Aditya Khanna and Nart Shalqini

Math Circle Feb 3 2024

​

Suppose you have a frog, Albert, who exhibits a rather strange behavior. Albert always likes to jump from one lily pad to the next turning its color red. Once he's done that, he continues jumping onto the next one, if possible.  

Albert, the Frog.

Albert

Infinitely Many Lily Pads?

Suppose you have infinitely many lily pads lined up in a row (rather strange, again). Albert jumps on Pad number 1, or P(1), and turns it red. 

   1                   2                         3      4        5      6     7     8

Next, P(2) turns red, then P(3) and P(4), and so on...

   1                   2                         3      4        5      6     7     8

qwark-qwark

   1                   2                         3      4        5      6     7     8

Will Pad 137 ever turn Red?

​

Yes! But why?

​

Answer: Induction! 

​

​

​

Albert does Induction

        133     134          135     136             137           138                139 

​

​

​

​

​

​

​

​

The Induction Hypothesis

1. Base Case: P(1) is true (frog example: P(1) is Red)

2.  Induction Step: 

       Whenever P(k) is true, then P(k+1) is true.

​

Frog example: the frog always jumps from Pad k to Pad k+1.

Conclusion: P(n) is true for all n>0

How many of each color?

How many of each color?

1

How many of each color?

1

3

How many of each color?

1

3

5

How many of each color?

1

3

5

7

How many of each color?

1

3

5

7

ODD NUMBERS!

Add them up

1

3

5

7

+

4

Add them up 

1

3

5

7

+

4

+

9

Add them up 

​

1

3

5

7

+

4

+

9

+

16

Add them up 

​

1

3

5

7

+

4

+

9

+

16

Squares!

Is this always true?

Is it always true that the sum of first n odd numbers starting from 1 is a square number?

Is this always true?

Is it always true that the sum of first n odd numbers starting from 1 is a square number?

We can prove it by induction. What is our P(n)?

Using induction

P(n): The sum of first n odd numbers is equal to the square of n.

Let's do this with pictures!

Activity!

1

3

Can you make a 2x2 square using these?

Activity!

1

3

Can you make a 3x3 square using these?

5

n

n+1

Let P(n) be n > n + 1

Let P(n) be n > n + 1

If we add one on both sides, we get

n + 1 > n + 2

​

which is P(n+1)

​

Assuming P(n) we have shown P(n+1)

Assuming P(n) we have shown P(n+1)

This means, by induction, for all numbers n we have n > n+1.

​

But this is false!!!

That is because we did not check the base case which is P(1): 1 > 2 is false.

​

It has 6 corners and 6 sides

Let us take P(n) to be "A polygon has n corners and n+1 sides"

If we add a corner, we get n+1 corners

For sides, we add two sides and subtract 1. So, in total we add one side, giving a total of n+2

So, P(n) gives P(n+1)

But this is false because the base case is false!

We will now use induction to prove that all cats are the same color! So, let's get started.

​

What is the first thing that we do?

​

What is our P(n) here?

What is our P(n) here?

We have P(n) being "all n cats in the group have the same color"

What is our P(n) here?

We have P(n) being "all n cats in the group have the same color"

For n = 5

Let's do the base case! What would P(n = 1) be?

Let's do the base case! What would P(n = 1) be?

"One cat in the group has the same color".

Let's do the base case! What would P(n = 1) be?

"One cat in the group has the same color". A cat has the same color as itself!

Let's do the induction step now! If we believe in P(n), can we argue that P(n+1) is true?

Let's do the induction step now! If we believe in P(n), can we argue that P(n+1) is true?

If "n cats in a group have the same color, then n+1 cats have the same color"

Let's do the induction step now! If we believe in P(n), can we argue that P(n+1) is true?

If "n cats in a group have the same color, then n+1 cats have the same color"

Let's prove it. Suppose we have n+1 cats

Let's prove it. Suppose we have n+1 cats

Let's prove it. Suppose we have n+1 cats

We leave one cat and pick the remaining n cats. Are these cats the same color?

Let's prove it. Suppose we have n+1 cats

Yes! Because P(n) is true. So, these n cats are the same color.

Similarly, these n cats are the same color.

So, what can we say from this?

Similarly, these n cats are the same color.

So, what can we say from this?

All n+1 cats are the same color!

So, by induction it means "any collection of n cats have the same color", but wait!

Take these three cats...

… which are all of different colors, so P(3) is false??? What is happening here? Where did we go wrong?

Let us do the induction step on just two cats

Let us do the induction step on just two cats

This cat is the same color as itself … 

Let us do the induction step on just two cats

... and this cat is the same color as itself... 

Let us do the induction step on just two cats

But there is no overlap between the circles, so we cannot say that they are the same color!

What this means is that we cannot go from P(1) to P(2)

In frog jumping terms, this means that

In frog jumping terms, this means that

The frog cannot jump from Lilypad 1 to Lilypad 2

1

2

Strong Induction

Suppose your friend says to you:

​

​

​

​

​

Every square can be tiled with 6 or more squares.

 P(n): A square can be tiled with n squares

P(4)

P(6)

Strong Induction

We can now do something nice

P(6)

Is P(n) true for all n>5?

P(6)

P(9)

P(12)

This does not cover all the cases. But we can be clever!

P(7)

P(10)

P(13)

What about 8, 11, 14..?

Strong Induction continued...

Three base cases: 

P(6)

P(7)

P(8)

Induction Step: 

Some squares

Some squares

Some squares

Some squares

P(k)

P(k+3)

Three base cases: 

P(6)

P(7)

P(8)

Induction Step: 

Some squares

Some squares

Some squares

Some squares

P(k)

P(k+3)

Strong Induction continued...