Working Backwards: Recursion, Induction, and Minimality

Induction (Part 1)

Table of Contents of the induction series :

Part 1

Part 2

Part 3

Part 4

Part 5

Part 6

Part 7

So, what is induction?

You might wonder, what is induction?

This is what induction is :

$\bullet$ A type of mathematical proof used to establish a given statement for all (or some) positive integers.

$\bullet$ It consists of $2$ steps :

$1$. Establishing the base case.

$2$. Inductive Step.

I can hear you screaming. What is base case? What is the inductive step. I'll explain these in a moment.

Analogy

Here's a simple analogy :

That's correct. This process continues until the last domino fall.

This is very like induction. But instead of pushing dominoes, you're proving statements. You prove it for the first case (or the so-called base case) and then prove that if you prove it for some case, then the next case is true. (the inductive step)

Now that you know what induction is, we'll look in detail what the base case and inductive step is.

Base Case

So, what is base case? Let's assume you want to prove a statement involving a positive integer $n$ holds for all $n \ge x$, where $x$ is some integer.

Now, the base case is usually the statement for $n = x$. So, you usually want to start your induction by proving the statement for $n = x$.

Now, we look at the inductive step.

Inductive Step

Prove that if a statement holds for some positive integer $n = k \ge x$, then it holds for $n = k + 1$. (This is the "usual" inductive step)

Some of you might be dizzy or discouraged after seeing this seemingly complicated explanation. That's why I'll continue with a simple example to show the power of induction.

Prove that for all positive integers $n$,

$1 + 3 + 5 + ... + (2n - 1) = n^2$.

I believe most of you have seen this identity before, but if you haven't, try to prove it (with or without induction). There's a nice proof without words. (Which I will demonstrate after the proof by induction)

We start with the base case.

The base case is true since $1 = 1^2$.

Next, we proceed with the inductive step.

In the inductive step, we'll have to make use of the inductive hypothesis, which is the truth of the statement for $n = k$.

Our strategy is to proof the statement when $n = k + 1$ given that the statement is true for $n = k$. (the statement for $k$ is called the induction hypothesis.) Note that this assumption can be made because by the base case, the statement is true for $n = 1$, and thus, we can assume that the statement is true for $n = 1$, and we use it to prove the statement for $n = 1 + 1 = 2$. Continuing this process, we prove the statement for $n = 3$, $n = 4$, and thus, we can prove it for all natural numbers. (Note : The base case not neccesarily equals $1$, it may equal to other integers.)

Now you should see the power of induction, and this is why induction works.

So, let us assume that the statement is true for $n = k$, i.e.

$1 + 3 + 5 + ... + (2k - 1) = k^2$.

We'll prove that the statement is true for $n = k + 1$, i.e.

$1 + 3 + 5 + ... + (2k + 1) = (k + 1)^2$.

Indeed,

$1 + 3 + 5 + ... + (2k + 1) = 1 + 3 + 5 + ... + (2k - 1) + (2k + 1) = k^2 + 2k + 1 = (k + 1)^2$, as desired.

This works like magic, isn't it? So, what have we learnt from this example?

But wait, I did promise a proof without words solution for the statement, so take a look below :

Fascinating, isn't it?

Practice makes perfect, so try out these simple induction exercises to make sure you understand this material.

Prove that for all positive integers $n$,

1. $1 + 2 + ... + n = \frac{n(n + 1)}{2}$.

2. $1^3 + 2^3 + ... + n^3 = (1 + 2 + ... + n)^2$.

3. $9 \mid n^3 + (n + 1)^3 + (n + 2)^3$.

That's all for this part. We'll look into more induction in the next part.

$Let's$ $talk$ $about$ $methods$ $of$ $proof!$

Probably the most common techniques are:

$Proof$ $by:$ $Contradiction$ $and$ $Induction$

$Contradiction:$ Let's say that we wanted to show our annoying sibling that what they were saying, some statement X, were false. One way we can do this is by assuming that their statement X is actually true. We can use contradiction by showing that if X were true, then some impossible statement would have to be true. Obviously there lies the contradiction, and we have proven to our adamant sibling that their statement was actually false.

$Induction:$ Induction is a pretty useful method of proof. It is generally used to prove statements which are true for all positive(or nonnegative) integers. Let's say that we wish to show that $a$ is true for all integers $n.$

First we start with our $basis$ $case.$ A basis case is just a trivial, obvious case. So, we can show in our basis case that $a$ $is$ $true$ $for$ $n=1.$

Then we move to our $inductive$ $step,$ also called the $inductive$ $hypothesis.$ We assume that $a$ $is$ $true$ $for$ $n=k.$

So, if $a$ $is$ $true$ $for$ $n=k,$ $then$ $it$ $is$ $also$ $true$ $for$ $n=k+1$

This is usually proved with some algebra. It shows that since $a$ is true for $n=1,$ then it is also true for $n=1+1.$ Therefore it is true for 3, 4, 5, 6, and so on.

We finish with our statement that:

$Having$ $done$ $the$ $basis$ $case$ $and$ $the$ $inductive$ $step,$ $by$ $the$ $Principle$ $of$ $Mathematical$ $Induction,$ $we$ $have$ $proven$ $our$ $claim$ $that$ ($write$ $your$ $claim$ $here$) $to$ $be$ $true$ $for$ $all$ $integers$ $n.$

Induction (Part 2)

The link to the table of contents.

In the last post, we look at what induction is and gave a simple example of induction in action. In this part, we'll look at two more applications of induction.

The first problem :

Prove that for all positive integers $n > 3$, $n! > 2^n$.

Verify that $4! > 2^4$, so our base case is true.

Assume the statement is true for $n$. (we'll not use $n = k$ from now on and instead just assume the statement is true for $n$ for simplicity)

Now, we need to prove the statement for $n + 1$, i.e. $(n + 1)! > 2^{n + 1}$. Indeed,

$(n + 1)! = n! \cdot (n + 1) > 2^n \cdot 2 = 2^{n + 1}$, as desired (since $n > 3, n + 1 > 2$)

This completes the proof.

This isn't very difficult. Once you know the "standard procedure", you can solve this instantly. So, try to prove the following inequalities for positive integers $n \ge k$, where $k$ will be given for each problem.

1. $2^n > n, k = 1$.

2. $2^n > 2n + 1, k = 3$.

3. $2^n > n^2, k = 5$.

Next, we look at a more challenging problem.

Problem : Given a $64 \times 64$ chessboard, prove that if one square is removed, then the remaining be tiled with L-shapes.

Note : An L-shape looks like

One can try to manually tile the board with L-shapes, but we seek a better way. $64$ seems like a random number, so why don't we generalize the problem.

One way to do it is to replace $64$ by $n$, where $n$ is a positive integer.

Right. If $n = 3$, then there are only $3 \cdot 3 – 1 = 8$ squares on the board, which can't be completely covered by L-shapes. (since every L-shape consists of $3$ squares, and $3 \nmid 8$.)

What should we do now?

In fact, our generalization is too general. So, what properties does $64$ have. Well, $64$ is even, you might say, so let's give it a try. We replace $64$ by $2n$. (where $n \in \mathbb{N}$)

The answer is unfortunately again no.

One can easily see that it fails when $n = 3$.

Yes, it's a power of $2$, so let's try that. We replace by $64$ by $2^n$, where $n$ is a positive integer.

Try to prove it by induction now, though it's still not easy.

Let's start with the base case.

So, the statement is obviously true.

Next, we go to the inductive step.

However, we find ourselves no immediate way to proceed. How do we relate a $2^{n + 1} \times 2^{n + 1}$ square with a $2^n \times 2^n$ one? We can divide the $2^{n + 1} \times 2^{n + 1}$ square into $4$ $2^n \times 2^n$ ones! (by joining the midpoint of the sides of the square to the midpoint of the opposite side of the square).

How should we proceed?

Ok, here is a sketch of a $2^{n + 1} \times 2^{n + 1}$ board (Note that the image uses $k$. Treat $k$ as $n$.)

Now, there's a hole in the board somewhere. It must be in one of the quadrants. Now we need to make use of the induction hypothesis, which states that any $2^n \times 2^n$ square with a hole can be tiled with L-shapes.

Try to think of a way to make use of it.

One of the $2^n \times 2^n$ square (the one with the hole) can be tiled by the induction hypothesis. How about the other three? We need a hole out of each of them. Thinking along these lines quickly yield a solution :

We place a L-shape in the middle of the board, as shown below.

Now we can finish the proof, as all the $2^n \times 2^n$ squares with a hole can be tiled by L-shapes. Thus, we're done.

That was a quite a tough problem. In the next part, we'll look at strong induction, which is useful in most situation when this standard induction doesn't work.

Induction (Part 3)

Link to table of contents

In this part, we'll look at strong induction.

Strong induction

Forgive me that I can't find a very good photo analogy of strong induction.

Esentially, it's almost the same as the induction we've done before. However, there's one main difference, and that is the inductive step. Instead of just assuming that the statement holds for $n = k$, we assume it holds for all $n \le k$. (starting from the base case.) Note that this assumption is valid and still proves the statement.

If you remember the domino analogy, think of it as dominoes with springs that keep them from falling, and the springs get stiffer as $n$ increases. Now, domino $n$ requires not just the force of the $(n - 1)$-th domino to make it fall, but all of its neighbours to the left, in order to fall.

Now, we will demonstrate the following (famous) problem :

Prove that every positive integers $n$ can be written as the sum of distinct Fibonacci numbers. (Fibonacci numbers are defined as $F_0 = 1, F_1 = 1, F_{n} = F_{n - 1} + F_{n - 2}$, for $n \ge 2$.

Note : $F_0 = F_1 = 1$ are considered the same.

Think about this for a moment before looking at the discussion below.

The base case is obvious, ($1 = F_1$)

Now, we go to the inductive step.

The way we've be inducting previously is assuming it's true fr $n$ and proving it for $n + 1$. But now, we have a problem : there's no way to relate the problem for $n + 1$ to $n$.

Instead, we'll assume it is true for all positive integers $k \le n$. Now, we attempt to prove the statement for $n + 1$.

Consider the largest Fibonacci number not exceeding $n + 1$. If it's $n + 1$, we're done. If not, consider $n + 1 - F_k$, where $F_k$ is the Fibonacci number described. Then, $n + 1 - F_k < n + 1$ and thus by the induction hypothesis can be written as the sum of distinct Fibonacci numbers. There's still one thing though, that is to check that $F_k$ never occur again.

We'll prove that $2F_k > n + 1$.

Indeed, $2F_k > F_k + F_{k - 1} = F_{k + 1} > n + 1$, so we're done.

We'll look at an interesting problem in the next part of this article. Stay tuned!

Induction (Part 4)

Link to table of contents

In this article, we'll look at an interesting problem that can be solved by strong induction.

A player $A$ plays the following game :

He starts with a pile of $100$ stones. Every second, he seperates a pile of stones consisting of at least $2$ stones into $2$ piles. If he seperate a pile of $n$ stones into $2$ piles of stones $a$ and $n – a$, where $a$ and $n – a$ are positive integers, then he gets $a(n – a)$ points. He starts off with $0$ points, what is the maximum number of points he can get if the game ends when there are $100$ piles, each consisting one stone.

$100$ doesn't seem special, so let's just replace it with $n$ (where $n$ is a positive integer) and hope to find a pattern.

Let $S(k)$ be the maximum possible score for $n = k$.

I'm sure you're tired of this now, just answer one more question.

Now, in calculating $S(4)$, you might have use the following diagram/chart.

Note that the score is always $6$, i.e. an invariant. This is suspicious. Indeed, one can experiment with $S(5)$ and find that the same scenario occured. Interesting.

Anyway, the sequence $0, 1, 3, 6, ....$ seems familiar Indeed, $1 = 1, 3 = 1 + 2, 6 = 1 + 2 + 3$.

Thus, we conjecture that $S(n) = 1 + 2 + … + (n – 1)$ for all positive integers $n > 1$.

Also, we might as well conjecture that the maximum score is obtained after any sequence of possible moves, since it seems like it is the case.

So, we are trying to prove the following : “$S(n) = 1 + 2 + … + (n – 1)$, and the maximum score is obtained after any sequence of possible moves, for $n > 1$”

Try proving it first.

We prove the statement by strong induction :

Base Case : $n = 2$.

$S(2) = 1 = 2 – 1$. This proves the base case.

Inductive Step :

We'll assume the statement for all $k < n$ and prove the statement for $n$, i.e. $S(n) = \frac{n(n - 1)}{2}$. Indeed, if in the first move, we split the stones into two piles, consisting of $k$ and $n - k$ respectively, then the score we get is $S(k) + S(n - k) + k(n - k)$. Note that $1 + 2 + ... + (n - 1) = \frac{n(n - 1)}{2}$, so

$S(n) = S(k) + S(n - k) + k(n - k)$ $= \frac{k(k - 1)}{2} + \frac{(n - k)(n - k - 1)}{2} + k(n - k)$ $= \frac{n(n - 1)}{2}$.

So, we proved the unexpected claim.

Thus, returning to the original problem, the answer is $S(100) = \frac{99(100)}{2} = 4950$.

This concludes Part $4$.

In the next part, we'll look at some techniques in using induction.

Induction (Part 5)

Link to table of contents

Sometimes you tried to solve a problem by induction, but unfortunately failed. You're frustrated. You give up, and get a 0/7 for that problem.

Sometimes, a problem is not so straightforward. You need to use some techniques to get it working. That's why, in this part, we'll look at some of the tips and tricks to succeed in solving a problem with induction.

Techniques in using induction

Don't always Add $1$

In the previous examples, we always prove the statement for $n = k + 1$ using the assumption of the truth of the statement for $n = k$ (or $n <= k$ for strong induction).

However, why does it always have to be $k + 1$?

Consider the following question :

Prove that if $n > 5$ is a positive integer, then it is possible to cut a square into $n$ smaller squares (not neccesary of the same size).

We'll use the following fact :

“Any square can be cut into 4 smaller squares.”

Proof. See the diagram.

So, it is possible to divide a square into $n + 3$ smaller squares given that it is possible to divide a square into $n$ smaller ones. ($n > 5$ is an integer.) To see why, given the diagram for the division of a square into $n$ smaller ones. Since $n > 5$, we can select a square, cut it into $4$ smaller ones, which makes a total of $n + 3$ squares. This suggest we prove the statement for $n = k + 3$ instead of $n = k + 1$ from the truth of the statement when $n = k$.

Note that in this case, we'll need three base cases, $n = 6, 7, 8$. The proves that they work is in the diagram below :

With the base case taken care of, we can now use the observation above to finish the proof.

Here's an exercise :

Prove that there exists $2013$ distinct positive integers $a_1, a_2, ..., a_{2013}$ such that the sum of theire reciprocals is $1$.

Hint: add $2$.

Strengthen the statement

Occasionally, we might want to prove a stronger statement. Sometimes, stronger statements are easier to proof.

For example, consider this :

Prove that for all positive integers $n$,

$(\frac{1}{2})(\frac{3}{4})...(\frac{2n - 1}{2n}) \le \frac{1}{\sqrt{3n}}$.

Let's try the "usual" way of tackling this problem.

The base case is obvious.

Inductive Step : Suppose the inequality is true for $n$, we want to prove it for $n + 1$. This is equivalent to show that

$(\frac{1}{2})(\frac{3}{4})...(\frac{2n - 1}{2n})(\frac{2n + 1}{2n + 2}) \le \frac{1}{3n + 3}$. So far so good.

By the induction hypothesis, it is enough to prove that

$\frac{1}{3n}(\frac{2n + 1}{2n + 2}) \le \frac{1}{3n + 3}$.

In horror, this inequality fails at $n = 1$! We're doomed.

Looking back at the base case, we found that the inequality seemed to be strict. Thus, we could try and prove a stronger inequality :

$(\frac{1}{2})(\frac{3}{4})...(\frac{2n - 1}{2n}) \le \frac{1}{\sqrt{3n + 1}}$.

Try proving this first.

Note that this inequality is stronger then the original one. The base case is true, only this time it's an equality, which is as sharp as an inequality can be!

The inductive step is now obvious. We need to prove that

$(\frac{1}{2})(\frac{3}{4})...(\frac{2n - 1}{2n})(\frac{2n + 1}{2n + 2}) \le \frac{1}{3n + 4}$, which is equivalent to

$\frac{1}{3n + 1}(\frac{2n + 1}{2n + 2}) \le \frac{1}{3n + 4}$ by the induction hypothesis. Cross multiplying settles the issue nicely. $\blacksquare$

This ends Part 5. In the next part, we'll look at some interesting pitfalls in using induction.

Induction (Part 7)

Link to the table of contents

In this article, we look at two tougher problems.

The plane is divided into regions by straight lines. Show that it is always possible to color the regions with $2$ colors so that adjacent regions have distinct colors.

It seems odd that this problem can be solved by induction, there's not even a variable to induct on!

So, let's create a variable. The natural choice is to induct on the number of lines, so let's try that.

Let the number of lines be $n$.

To make things simpler, let the 2 colors be black and white.

The statement we want to prove is "If we divide the plane with $n$ lines, then we can color the regions with two colors so that adjacent regions are of different colors. " (For the sake of simplicity, call this type of coloring good.)

The base case is $n = 1$.

Then, we color the 'left' region white and the 'right' region black. This proves the base case.

Inductive Step :

Suppose it is possible to color the plane that is divided by $n$ lines in two colors such that it is good.

Now, we construct a coloring for a plane that is divided by $n + 1$ lines.

See diagram below :

First, we draw the first $n$ lines and color it with a good coloring (it exists by the induction hypothesis.)

Then, draw in the $(n + 1)$-st line. (The dotted line in the diagram)

Finally, we “invert” the coloration to the right of the line. (so white becomes black, black becomes white) (example in the diagram)

The region to the left of the line still have a good coloration, and the region to the right also have a good coloration, (it's just the inverse of their original colors.) and the region that share borders along the line, will be differently colored. (because we inverted it.)

Thus, the new coloration is good, which completes the inductive step.

This completes the induction.

We proceed to the next and final problem of this series.

Prove that for all positive integer $n$, $\sqrt{2\sqrt{3\sqrt{4\sqrt{...\sqrt{n}}}}} < 3$.

Hint: induct backwards

Solution :

Clearly straightforward induction doesn't work. We introduce a technique called backward induction.

The key is to change the inequality into the following form :

$\sqrt{k\sqrt{(k + 1)\sqrt{(k + 2)\sqrt{...\sqrt{n}}}}} < k + 1$, where $k$ is an integer $> 1$ and $\le n$.

Now, we want to induct on $k$. Our base case is not $k = 2$, but $k = n$. (Now you see why it's called backward induction, we start from $k = n$ and go down to $k = 2$.)

Verify that the base case is indeed true. We now proceed to the inductive step (I'm not including the technical details, just how to prove the inequality):

$\sqrt{(k - 1)\sqrt{k\sqrt{(k + 1)\sqrt{(k + 2)\sqrt{...\sqrt{n}}}}}} < \sqrt{(k - 1)(k + 1)} < \sqrt{k^2} = k$, by the induction hypothesis.

Thus, we're done.

This concludes the induction series.

Induction (Part 6)

Link to table of contents

In this part, we'll look at pitfalls of using induction.

Pitfall #1 : n = n + 1

What is wrong with the following argument :

We prove that for all positive integers $n$, $n = n + 1$ by induction.

Suppose the statement is true for $n$, i.e. $n = n + 1$. We'll prove this for $n + 1$, i.e. $n + 1 = n + 2$. Indeed, it follows from adding $1$ to both sides of the equation. Thus, we're done.

The only thing here that's wrong is that the proof of the base case is omitted, which is a fatal error. This shows the importance of the base case. Even if it's trivial, you still need to prove it. A $99$% correct proof is still wrong.

Pitfall #2 : Your name is Zi Song.

We'll prove that in a group of $n$ people, all of them have the same name. This will imply your name is Zi Song.

We induct on $n$.

The base case is obvious.

Inductive Step :

Consider the first $n$ people. By the induction hypothesis, they all have the same name. Similarly, all of the last $n$ people have the same name. Thus, all $n + 1$ people have the same name.

Now, what's wrong with this proof?

Note that when we want to prove the statement for $n = 2$ from $n = 1$, we consider the first $1$ person (i.e. the first person) and the last $1$ person (i.e. the last person). Note that the argument no longer works in this case. So, the proof is wrong.

This shows that you need to check that your inductive step have no gap, or else your name is really Zi Song.

In the next part, we'll look at some tougher problems.

Introduction

Recursion is a rather underestimated technique in math, especially in competitions. Perhaps it's because it sounds so vague or trivial on first hearing. So before I give a direct explanation, instead I will demonstrate its power in a problem first.

Solution

After thinking about it for a while, we can't find an obvious direct approach that gets the problem in one go. But what if we build the tower a different way ...

We ask the question: Given an already constructed tower of $n-1$ cubes, how many ways are there to "insert" the cube of size $n$ in it to make a tower of $n$ cubes? We will then build the tower by inserting the cubes in ascending order of size.

So we find that the cube of size $n$ can only be placed right on top of the cube of size $n-1$ or $n-2$, or on the bottom: $3$ ways.

Of course, we have to watch out for $n\le 2$ because then $n-1$ or $n-2$ might not exist.

Now for the first cube (size $1$), obviously there's one way to place that, and for the second cube (size $2$), two ways (above or below the first cube). So there are $1\times 2=2$ ways to place the first two cubes.

We have $6$ cubes left, and due to our reasoning above, there are three ways to place each of those, making $3^6$ ways to place the last $6$ cubes.

So our total is $2\times 3^6=2\times 729=\boxed{1458}$.

Recursion

So what exactly did we do there? Instead of thinking about building a tower, we can say that we solved the problem for smaller numbers of cubes, and we used each answer to get the answer for larger values of cubes. (For example, if there were 3 cubes in the tower, the answer is $6$, and we multiplied that by $3$ to get the answer for 4 cubes, which is $18$.)

This is the essence of recursion.

So now I will formally define recursion.

Suppose we had a situation that depended on some integer variable $n$ (like $n$ blocks or whatever). Recursion is a technique composed mainly of two parts:

Base Case

You find some property of the situation (like how many towers can be constructed) for some small $n$, small enough to be trivial. Usually, you use $n=1$.

Inductive Step

Now we show that the situation for $n-1$ is in some way related to the situation for $n$, and we can carry over information from the smaller case to the bigger case. The power in this step is that we can assume the situation for $n-1$ is already true.

Now for the magic: the base case handles $n=1$. Then the inductive step uses the $n=1$ to handle $n=2$. Then the inductive step uses $n=2$ to handle $n=3$. And so on, until any and every integer is reached. It's like knocking down dominoes.

Induction

In fact, recursion is almost the same thing as induction. It is just that induction is more specific — it uses the truth of some statement or algebraic expression along each step to prove the next.

For example, we can structure the proof of the following statement using induction: $$1+2+\cdots+n=\frac{(n)(n+1)}{2}$$

*Base case: * The statement is true for $n=1$.

*Inductive step: * Given that the statement is true for $n-1$ (e.g. we know that $1+2+\cdots+(n-1)=\frac{(n-1)(n)}{2}$), we can prove the original statement for $n$.

The details are left as an exercise.

Never, ever ever forget the base case!

One oversight that people new to this technique often make: forgetting the base case. Remember, even if you've stacked all the dominoes, you still have to knock down the first one to set them in motion!