Core Pure - Proof by Induction

Table of contents:

  • Introduction
  • Examples
  • Common Mistakes
  • Exercises (includes strong induction in question 5)
  • Are Induction Proofs Explanatory?

Introduction:

Proof by induction is an extremely useful proof technique that can seem a little strange at first. Let’s have a look at the theorem below, first.

Theorem: Suppose a statement P_n satisfies the following properties:

  • P_1 is true
  • For all positive integer k, P_k is true \implies P_{k+1} is true

Then P_n is true for any positive integer n

Pre-Proof: using the second condition, we can show successively that P_2,P_3,... is true, but in this way we will never be able to show the proposition’s truth for all positive integers, since there are infinitely many.

To bypass this, we are going to employ the contrapositive in the proof so here is a brief explanation of the contrapositive: Suppose we have a statement "If A then B". To show that this statement is true, we can show that is contrapositive "If not B then not A" is true, as both statements are logically equivalent.

Proof: We proceed by contradiction and suppose that there is some positive integer x such that P_x is false (clearly x is not 1).

Taking the contrapositive of the second property we have:
P_{k+1} is false \implies P_k is false.
Since x is a positive integer, we now know that all positive integer smaller or equal to x satisfy P_k is false (by repeated use of the property above, since we only need to use it a finite number of times). But 1 is smaller than x, so P_1 is false, a contradiction. \blacksquare

Now that we have proved the principle of mathematical induction, we have a (powerful) method of proving theorem involving positive integer:

If we want to prove some statement P_n true for all positive integer by induction we proceed with the following steps:

  1. We show P_1 is true, this is our base case.
  2. We show that if P_k is true (for some positive integer k) then P_{k+1} is true. This is called the inductive step.
  3. Conclude that the theorem is true by induction. Don’t forget this in the exam, or it’ll cost you a mark (which can be the difference between getting to your dream uni or not)

To help the reader understand the concept a little more, I will present an analogy here. Suppose that each integer is a domino (all placed in order). We are given that if a domino falls, the next one falls too, The first domino (representing 1) falls, causing 2 to fall, then 3 to fall, then 4 to fall, etc. As you can see, it seems obvious that all dominos must eventually fall, even though there are infinitely many of them.

A level Further Math exams are very specific about the induction argument. In the exam, I highly recommend you to follow the steps provided in the past papers’ mark schemes. Have a look at the past paper question below (which is shockingly an overdone standard result in your textbook anyway so there is no risk of spoiling anything)

Try it and then click the spoiler tag for the mark scheme

Mark Scheme

You should memorize the conclusion as it is here for the exam, especially the underlined parts (they are essential for the mark).

Note that assuming the general statement is true for n=k and then showing that the general statement is true for n=k+1 is the same as step 2: “We show that if P_k is true (for some positive integer k) then P_{k+1} is true”.

Let’s see induction in action! As the reader must have the AS further Math textbooks, I will present unusual examples here.

Examples:

Have a look at a few examples in your textbook first. Do note that induction proofs come in only a few forms in the A level exam, and that the examples provided here will not be in one of those forms.

But before you start on the first example, here is a short exercise:

Exercise: How can you adapt induction such that we prove a statement for all integer larger or equal to x, for some integer x?

Solution:

Let the base case be x instead! Then you need to show that for all integer k\geq x, P_k is true \implies P_{k+1} is true

We’ll start with a simple geometric theorem. I assume the reader knows what a convex polygon is.

Example 1:

Theorem: A convex polygon of n sides has \frac12n(n-3) diagonals.

Proof:

Base case: n=3: A triangle is necessarily convex, and they have no diagonals!

Suppose the conjecture is true for some n=k. Consider n=k+1:

label the vertices 1,2,3,...,k,k+1 and consider the polygon with vertices 1,2,3,...,k, which has \frac12k(k-3) diagonals, since it is convex. Since the polygon is convex, for each point, there is a diagonal between all but two of the remaining points (these two are the adjacent ones). Do not forget the diagonal from 1 to k.

Therefore, the sum of all diagonals is:
\frac12k(k-3)+(k-2)+1=\frac12(k^2-k-2)=\frac12(k+1)(k-2).
By induction, the theorem is true for all integer n such that n\geq3 \blacksquare.

I really like this next example. It is a logic puzzle.

Example 2: Carl and Karl are playing a game both have a positive integer written on their foreheads. They each know the numbers differ by 1 and obviously the other’s number, but not their own. They each take turns asking asking if they know their own number. You should assume that Carl and Karl are expert logicians and will deduce their numbers as soon as possible. Also assume that Carl and Karl always tell the truth.

Theorem: The game is not endless regardless of the numbers on Karl and Carl’s foreheads. Furthermore, letting the lower number be n, the game must end in 2n turns or less.

Why don’t you try this one out before seeing the solution? But even then, check the hints first!

Hint 1

If Karl’s number is 1, what must Carl’s be?

Hint 2

Each question they ask each other really does add information to the problem.

Pre-Proof (Generous Hint)

If the first or second answer is “Yes” then one of the numbers must be 1, as that person knows his number is 2 (as 0 is impossible).

If both the first and second answers are “No” then no one has 1. Then:

If the third or fourth answer is “Yes” then one of the numbers must be 2, as 1 is impossible.

If the third and fourth answers are “No” the no one has 2.

And so on…

At this point we can create an inductive argument, which seems plausible (even obvious) to be true.

Proof

We will prove the theorem by induction. WLOG let Karl’s number be n.

Base case: n = 1: Clearly, Carl must have a 2 (as 0 is not allowed). Hence, Carl immediately knows his number. Karl then deduces n = 1, as otherwise Carl cannot deduce his number. Karl knows his number as soon as he is asked, so maximum in the second turn.

Suppose the game ends for n = k. Consider n = k + 1:

If the game finishes in 2k or less turns we are done.

If not, consider turns 2k + 1 and 2k + 2. Karl will ask in either turn.

When Karl asks, Carl will answer “Yes”, because Carl knows his number is k + 2 as it cannot be k (by inductive hypothesis). Karl then knows his number too, as he knows that it is not k + 3, otherwise Carl would not say “Yes”. We are thus done.

By induction, the theorem holds.

Example 3: This example is adapted from the Peano Axioms.

For this example, you may assume the following (regarding addition) for all integer a and b:

  • a+(b+1)=(a+b)+1
  • a+0=a

You may not use any other properties of addition.

Theorem: Addition under the non-negative integers is associative. That is, for all integer a,b, and c, (a+b)+c=a+(b+c). Try it before seeing the solution! \

Proof:

We will use induction on c:

Base case: c=0:
a+(b+0)=a+b=(a+b)+0
_
It is true that the base case for c=1 is trivial, by assumption, but the question requires us to prove the theorem for all non-negative integer!
_
Suppose the theorem is true for c=k. Consider c=k+1:
_
For clarity, let d=a+b:
(a+b)+(c+1)=d+(c+1)
=(d+c)+1
=((a+b)+c)+1
=(a+(b+c))+1
=a+((b+c)+1)
=a+(b+(c+1)), as desired.
_
By induction the theorem holds for all non-negative integer c.

I included this example because we use this property so often, yet few A level students actually come to prove it.

Common Mistakes:

In this section, I will present some erroneous proofs and the reader’s goal is to find the error.

"Theorem": n+1>n for all n>0

Suppose the theorem is true for n=k. Consider n=k+1:

k+1<k so (k+1)+1<k+1. Hence, k+2<k+1
Hence, the claim is true by induction.

Error:

The base case has been omitted, never forget it in your proofs!

"Theorem": All cats are of the same color (I will let you guess why I chose cats):

We can restate this as: Given any set of n cats, where n is a positive integer, all cats in the set have the same color, in order to be able to use induction.

Base case: the case for n=1 is trivial.

Suppose this is true for n=k, consider n=k+1. Let the k+1 cats be called c_1,c_2,…,c_{k+1}. All cats in the set {c_1,…,c_k} are of the same color and all cats in the set {c_2,…,c_{k+1}} are too. The sets are not disjoint (that is, they have cats in common) so all of the k+1 cats have the same color, as desired.

By induction, all cats are of the same color.

Error:

The induction step isn’t valid for all positive integer k. What happens when k=2?

When k=2 the sets of cats have no cats in common so the argument fails

"Theorem": a^n=1 for all non-negative integer n and all positive real a.

Base case: trivial when n=0.

Suppose the theorem is true for n=k. Consider n=k+1:

a^{k+1}=a^ka^1=\frac{a^ka^k}{a^{k-1}}=1, as desired.

Hence, the theorem is true by induction.

Error:

When k=0, k-1 is not a non-negative integer, so the inductive step is not valid for all non-negative integer. Particularly, we cannot show that a^1=1 from a^0=0, hence the step fails.

"Theorem": Every positive integer is a lot less than 1 million.

Base case: 1 is a lot less than 1 million.

Suppose k is a lot less than 1 million. k+1 is only slightly more than k. Hence, k+1 is also a lot less than 1 million. By induction, all positive integer are a lot less than 1 million.

Wow 999999999999999999999999999999999999 is a lot less than 1 million

Error:

In this case, the error stems from the fact that “a lot less” and “slightly more” are not precisely defined. Surely, there must be a number k such that k is a lot less than 1 million but not k+1.

Exercises:

The first exercise below focus more on both the technique of proof by induction and carrying out proofs using induction. The questions below in no way act as substitute for past exam paper and textbook questions, which should be done by all candidates, regardless of ability. However, the exercises below should hopefully act as providing more breadth and depth to induction than what you would see in A level. These could be especially useful for those preparing for STEP (or the AEA and other such exams). Do not feel compelled to complete them all!

  1. How can you adapt induction such that we prove a statement for all integer smaller or equal to x, for some integer x?

Solution:

As in the first exercise, we let the base case be x. Then you need to show that for all integer k\leq x, P_k is true \implies P_{k-1} is true. The proof of this is analogous to the original proof of the principle of mathematical induction.

  1. How can you adapt induction such that we prove a statement for all integers? Hence prove DeMoivre’s theorem for all integers.

Solutions:

We can choose any integer as the base case, let it be x
We need to show that for all integer k\geq x, P_k is true \implies P_{k+1} is true and for all integer k\leq x, P_k is true \implies P_{k-1} is true. The first part is to show the truth for all integer larger than x, and the second part for all integer smaller than x.

Alternatively, with a base case of 0, if we show for all integer k\geq 0, P_k is true \implies P_{k+1} is true and for all integer k\geq 0, P_k is true \implies P_{-k} is true. I will not provide a solution to the proof of DeMoivre’s theorem since it is quite standard.

  1. Adapt induction to prove a statement is true for all even integers and false for all odd integers.

Solutions:

We can choose any even integer as the base case, let it be x
We need to show that for all even integer k\geq x, P_k is true \implies P_{k+2} is true and for all even integer k\leq x, P_k is true \implies P_{k-2} is true. The first part is to show the truth for all integer larger than x, and the second part for all integer smaller than x. For odd integer, we can do similarly as above but with an odd base case y, but we show for all odd integer k\geq y, P_k is false \implies P_{k+2} is false and for all odd integer k\geq y, P_k is false \implies P_{k-2} is false

  1. I kind of wanted to put this as an example as it is quite neat, but I think this will be better as an exercise.
    Finitely many lines divide a plane into regions. Show that these regions can be colored by 2 colors such that no two adjacent regions have the same color.

Hint:

Induct on the number of lines, say n. The base case n=1 is trivial. What happens when 1 line is added? The question isn’t difficult so I recommend making diagrams as it will make the solution easier to find.

Strong induction is NOT in the A level specs, hence why I included it as an exercise, I recommend learning it anyway as it isn’t more difficult to employ than standard induction.

  1. Strong Induction

Let’s begin by trying to prove by induction that the closed form for the recurrence relation F_n=F_{n-1}+F_{n-2}, \ F_1=1, F_2=1 is F_n=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt5}{2}\right)^n-\left(\frac{1-\sqrt5}{2}\right)^n\right), which is called Binet’s formula.

The base case with n=1 is easy.

Suppose the theorem is true for n=k, consider n=k+1:

F_{k+1}=F_k+F_{k-1}. Well here we have a problem, the assumption says nothing about n=k-1

We need to find a better way!

a. Suppose a statement P_n satisfies:

  • P_1 is true
  • For all 1 \leq k<n, \ P_k is true \implies P_n is true

Show that P_n is true for all positive integer n.

b. Hence complete the proof of Binet’s formula, which will then be by strong induction.

c. Note that we only need P_k is true and P_{k-1} is true to complete the proof. Can you adapt standard induction such that at the inductive step, we assume P_k is true and P_{k-1} is true rather than for all 1 \leq k<n, \ P_k is true?

Solution:

a.Suppose on the contrary that there is some positive integer k such that P_{k_1} is false. We thus know, by the contrapositive of the second property of P_n, that there is some k_2<k_1 such that P_{k_2} is false. This can be continued which gives a strictly decreasing sequence, which must be finite, as the positive integers have a minimum number. Indeed, continuing long enough we have P_1 is false, which is a contradiction

b. The proof is very similar to that of standard induction, taking particular care that since we need n=k and n=k-1, that we have to have the base case for n=2, as the inductive step works only for k+1 \geq 3, unless one finds the values of the sequence for n=0 and n=-1.

c. We need n=1 and n=2 as base cases. Then assuming P_k and P_{k-1}, we show $P_{k+1}. The proof that P_n holds for all positive integer is similar to the string induction and standard induction cases, so I will leave the reader to fill in the details.$

Challenges:

  1. The question is here: AM-GM Inequality Proof by Induction

  2. A Fibonacci Identity by Induction

More questions will (hopefully) come in time, but this shoudl be sufficient.

Are Induction Proofs Explanatory?

Have you ever come across a proof (done by induction) and wondered “Where did they get the result from?”. I certainly have. It seems that such proofs fail to explain, in some sense, why the theorem is true, although it necessarily shows that the theorem is true. Most proofs not invoking induction do both however.

In a proof, we start with some assumptions and with a series of implications we reach a theorem. Certainly this is true with induction proofs too. However, induction proofs seemingly allow us to prove results without having a real understanding of what is going on. For the purposes of this section, let’s call proofs that gives readers some insight in the mathematics involved “explanatory”.

I argue that some induction proofs are indeed explanatory. A good example is DeMoivre’s theorem. Why? Because the reader, by the time they are ready to prove the theorem, have already conjectured that the theorem is true. That is, the theorem seems plausible (even obvious).

I thus propose a solution to the explanatory problem of induction. If the reader is convinced beforehand that the theorem must hold, then the reader has an understanding of what is going on, and thus will not feel like the theorem came out of the blue. This does not always work though, which in that case it is better to find another approach in order to understand the concepts involved. We do not always need to find another proof method, though; perhaps we can invoke geometry to attempt granting the reader some insight and then proving formally by induction could work, for example.

Were These Notes Helpful?

  • Yes! :smiley:
  • A Little :slight_smile:
  • Not Really :expressionless:
  • No :frowning:

0 voters

4 Likes

Wonderful!!!

Finally done :stuck_out_tongue:

2 Likes

A wonderful set of notes. If anybody in the community has anything they want to add, or questions on anything discussed in this topic then post your thoughts :+1:

1 Like