Induction
The principle of mathematical induction (often referred to as induction, sometimes referred to as PMI in books) is a fundamental proof technique. It is especially useful when proving that a statement is true for all positive integers \(n.\)
Induction is often compared to toppling over a row of dominoes. If you can show that the dominoes are placed in such a way that tipping one of them over ensures that the next one will fall and then you tip the first one over, you can assure that all the dominoes will eventually fall.
Contents
Statement
Let's say you have a statement \(P(n)\) that depends on a positive integer \(n\) and you have to prove that this statement holds for all positive integers \(n\). How would you do that?
Step 1:
At first you prove that \(P(k)\) is true where \(k\) is the starting value of your statement \(\big(\)for example, if your statement is \( \small\frac {n(n + 1)}{2}\) for all integers greater than 98, you must prove 99 is a valid solution\(\big)\). In other words, you must prove the starting value of your statement is valid.
Step 2:
Then you show that if the statement is true for any arbitrary positive integer \(x\), then it is true for \(x+1\).
If you can do both of these things, you've proved that the statement is true for all positive integers \(n\). Congratulations!
\(\)
Take some time to think about why this argument works. Remember that you proved that \(P(k)\) is true, where \(k\) is your starting value. You also proved that \(P(k+1)\) is also true \((\)if \(x\) is equal to \(k,\) which is a valid assumption\().\) Therefore, \(P\big((k+1)+1\big)\) or \(P(k+2)\) would also be true. By the same reasoning, \(P(k+3)\) is also true and so on. Therefore, proving the two steps mentioned above is enough to prove that the statement holds for all positive integers above your starting value \(k\).
For further details, see Proof of Mathematical Induction.
Formulation
Main article: Writing a Proof by Induction
Now that we've gotten a little bit familiar with the idea of proof by induction, let's rewrite everything we learned a little more formally.
Proof by Induction
Step 1: Prove the base case
This is the part where you prove that \(P(k)\) is true if \(k\) is the starting value of your statement. The base case is usually showing that our statement is true when \(n=k\).Step 2: The inductive step
This is where you assume that \(P(x)\) is true for some positive integer \(x\). This assumption is called the inductive hypothesis. Then you show that if \(P(x)\) were true, so is \(P(x+1)\). This is the inductive step.In short, the inductive step usually means showing that \(P(x)\implies P(x+1)\).
Notice the word "usually," which means that this is not always the case. You'll learn that there are many variations of induction where the inductive step is different from this, for example, the strong induction
That's basically all there's to it. At the start, it is best to follow a standardized format so that you know exactly what to write. Once you get comfortable with it, you can simplify the proof further.
Sometimes, flawed induction proofs happen.
As always, the best way to learn is through examples. So let's begin!
Examples - Summation
Summations are often the first example used for induction. It is often easy to trace what the additional term is, and how adding it to the final sum would affect the value.
Prove that \(1+2+3+\cdots +n=\frac{n(n+1)}{2}\) for all positive integers \(n\).
We want to prove something for "all positive integers \(n,\)" and induction seems like a good way to start.
First, we verify the base case. Although it seems obvious here (the base case is 1 because it is the first positive integer), this is a crucial step. Sometimes not verifying the base case can lead to fallacious proofs.
Our statement is true for \(n=1\) (our base case) because with \(n=1\) the left-hand side is \(1\) and the right-hand side is \(\frac{1(1+1)}{2},\) which is also \(1\).
Now let us assume that the statement is true for some positive integer \(k\). This is our induction hypothesis. If we can show that the statement is true for \(k+1\), our proof is done.
By our induction hypothesis, we have
\[1+2+3+\cdots+ k=\frac{k(k+1)}{2}.\]
Now if we add \(k+1\) to both sides, we get
\[\begin{array} { l l } 1+2+3+\cdots +k+(k+1) & =\frac{k(k+1)}{2}+(k+1) \\ & = (k+1)\left( \frac{k}{2} + 1 \right) \\ & = \frac{ (k+1)(k+2)} { 2} \\ & = \frac{ (k+1)\big((k+1)+1\big)} { 2},\\ \end{array} \]
which means that if our statement is true for \(k\), it is true for \(k+1\) as well. This proves the statement true for all positive integers \(n\). We're done!\(\ _\square\)
Prove that \(\displaystyle{\sum_{k=1}^{n}(2k-1)}=n^2\) for all positive integers.
Since \(2\times1-1=1^2\), the statement holds when \(n=1\).
Now let's assume that \(1+3+5+\cdots+(2k-1)=k^2\) for some positive integer \(k\). Then add \(2k+1\) to both sides of the equation, which gives
\[1+3+5+\cdots+(2k-1)+(2k+1)=k^2+(2k+1)=(k+1)^2.\]
Thus if the statement holds when \(n=k\), it also holds for \(n=k+1\). Therefore the statement is true for all positive integers \(n\).\(\ _\square\)
Prove that \(\displaystyle{\sum_{k=1}^{n}2^k}=2^{n+1}-2\) for all positive integers.
Since \(2^1=2^2-2=2\), the statement holds when \(n=1\).
Now let's assume that \(2^1+2^2+\cdots+2^k=2^{k+1}-2\) for some positive integer \(k\). Then add \(2^{k+1}\) to both sides of the equation, which gives
\[2^1+2^2+\cdots+2^k+2^{k+1}=2^{k+1}+2^{k+1}-2=2^{k+2}-2.\]
Thus if the statement holds when \(n=k\), it also holds for \(n=k+1\). Therefore the statement is true for all positive integers \(n\).\(\ _\square\)
\[1(1!)+2(2!)+3(3!)+4(4!)+\cdots +2014(2014)! = n!-1\]
What is the value of \(n?\)
Examples - Inequalities
Induction can also be used for proving inequalities. Just apply the same method we have been using. Once again, it is easy to trace what the additional term is, and how it affects the final sum.
Prove that \(2^n>n\) for all positive integers \(n.\)
Since \(2^1>1\), the statement holds when \(n=1\).
Now let's assume that \(2^k>k\) for some positive integer \(k\) which is larger than \(1\). Then multiply both sides of the equation by \(2\), which gives
\[2^k\times2=2^{k+1}>2k.\]
Since we assumed that \(k>1\), \(2k>k+1\) is always true. Hence we have
\[2^{k+1}>2k>k+1.\]
Thus if the given statement holds when \(n=k\), it also holds for \(n=k+1\). Therefore the statement is true for all positive integers \(n\).\(\ _\square\)
Prove that when \(h>0\), the inequality \((1+h)^n>1+nh\) holds for all positive integers \(n\geq2\).
Since \((1+h)^2=h^2+2h+1>1+2h\), the statement holds when \(n=2\).
Now let's assume that \((1+h)^k>1+kh\) for some positive integer \(k\) that is larger than \(2\). Then multiply both sides of the equation by \(1+h\), which gives
\[ \begin{array} { l l } (1+h)^k\times(1+h)=(1+h)^{k+1} & >(1+kh)(1+h) \\ & =kh^2+(k+1)h+1 \\ & >1+(k+1)h. \end{array} \]
Thus if the statement holds when \(n=k\), it also holds for \(n=k+1\). Therefore the statement is true for all positive integers \(n\geq2\).\(\ _\square\)
Prove, by mathematical induction, \( n^2 > 2n + 1\) for \(n \geq 4. \)
We attempt to verify that this statement holds true for the base case, that is, \(4^{2} > 2(4) + 1 \), which is true by nature. Now, we suppose that for some arbitrary integer, the statement will hold true: \(k^{2} > 2k + 1, k> 4. \) If this is true (by assumption), then if the next value of \(k,\) which is \((k+1),\) holds true, then by the principles of mathematical induction the whole statement is true within the domain of \( n: \)
\[\begin{align*}LHS &= (k+1)^{2} \\ &= k^2 + 2k + 1 \\ &> (2k + 1) + 2k + 1&&\qquad \text{ (by our assumption)}\\ &= 4k + 2 \\ &= 2k + 2k + 2 \\ &\geq 2k + 10&&\qquad \text{ (since we defined } k \geq 4\text{)} \\ &> 2k + 3 \\ &= 2k + 2 + 1 \\ &= 2(k+1) + 1 \\ &= RHS,\end{align*}\]
which implies \(LHS > RHS. \)
Thus, if the statement holds when \(n=k \), it also holds for \(n=k+1\). Therefore, the statement holds true within the condition \(n\geq 4\).\(\ _\square\)
Sometimes the application of induction to inequalities cannot happen directly. This happens when the side that is supposed to be smaller is increased to a larger extent. For more details, see "Stronger" Induction.
Examples - Divisibility
For proving divisibility, induction gives us a way to slowly build up what we know. This allows us to show that certain terms are divisible, even without knowing number theory or modular arithmetic.
Prove that \(2^{2n}-1\) is always divisible by \(3\) if \(n\) is a positive integer.
Again we have to prove something about "all positive integers \(n.\)"
For \(n=1,\) our statement is true since \(2^{2\times 1}-1\) is equal to \(3\) and thus divisible by \(3\).
Now we have to show that if the statement is true for some positive integer \(k\), it is true for \(k+1\). If the statement is true for \(k\), we can set \(2^{2k}-1=3x\) for some positive integer \(x\). Note that
\[2^{2(k+1)}-1=2^{2k+2}-1=2^2\cdot 2^{2k}-1=4\cdot 2^{2k}-1=3\cdot 2^{2k}+2^{2k}-1.\]
Since \(2^{2k}-1=3x\), this can be rewritten as \(3\big(2^{2k}+x\big),\) which is obviously divisible by \(3\).
We've been able to show the inductive step and that completes our proof. \(_\square\)
Show that, for all positive integers \(n\),
\[ 64 \, \Big| \, 3^{2n+1} + 40 n - 67. \]
Let \(P_n \) be the proposition \( 64~|~3^{2n+1}+40n-67\) for all positive integers \(n\).
First, consider the base case where \(n = 1\). Observe that
\[ 3^{2\cdot 1 + 1} + 40 (1) - 67 = 27 + 40 - 67 = 0 \]
and that \(64\) divides \(0\) since \( 64 \times 0 = 0.\) Then \(P_1\) is true.
Now, assume \(P_{k}\) is true for some \(k \in \text{domain},\) then \( 64 ~|~3^{2k+1} + 40k - 67\). This gives
\[ \begin{array} { l l } 64~|~ 3^{2k+3}+40k\times 9 - 67\times 9\\ 64~|~ 3^{2k+3}+40k + 40 + (40 \times 8k - 40) -67 + (-67\times 8)\\ 64~|~ 3^{2k+3}+40(k+1) -67 + (320k -576)\\
64~|~ 3^{2(k+1)+1}+40(k+1) -67. \end{array} \]Hence \(P_{k}\) true \( \implies P_{k+1} \) true.
By mathematical induction, since the base case where \(n=1\) is true and \(P_{k}\) is true, \(P_{k+1}\) true. Therefore, \(P_{n}\) is true for all positive integers \(n\). \(_\square\)
In the above question, it was difficult to utilize the induction hypothesis. Most people found it difficult to deal with the \(3^{2k+3}\) term, and the solution follows by understanding that \(3^{2k+3}=9\times 3^{2k+1} \).
We can actually show the base case for \(n=0\), which is a simpler calculation to do. While it is not immediately obvious why we would want to do this, imagine if the question asked to show this for positive integers \( n \geq 100\). Would you want to evaluate \(3^{201}?\) Not likely.
Examples - Recurrence Relations
When you are given the closed form solution of a recurrence relation, it can be easy to use induction as a way of verifying that the formula is true.
Consider the sequence of numbers given by \( a_1 = 1, a_{n+1} = 2 \times a_n + 1 \) for all positive integers \(n\). Show that \( a_n = 2 ^ n - 1 \).
Base case:
Let's check \( n = 1 \).
LHS: \( a_1 = 1.\ \) RHS: \( 2^ 1 - 1 = 2 - 1 = 1 \).
Hence, the base case is true.Induction step:
Assume that \( a_k = 2^k - 1 \) for some \(k\).
Then we have \( a_{k+1 } = 2 \times a_k + 1 = 2 \times ( 2 ^ k - 1) + 1 = 2 \times 2^ { k } -2 + 1 = 2^{k+1} - 1 . \)
Hence, the inductive step is true, and the result follows. \(_\square\)
Consider the Fibonacci sequence where \( F_0 = 0 , F_1 = 1 , F_n = F_{n-1} + F_{n-2} \) for all positive integers \(n\). Prove that
\[ F_0 + F_1 + F_2 + \cdots + F_n = F_{n+2} -1 \]
for all \( n \geq 0. \)
Base case:
Let \(n=0\). The LHS is \( F_0 = 0 \) and the RHS is \( F_2 - 1 = 0 \).Induction step:
Assume that the statement is true for \(n,\) i.e. \[ F_0 + F_1 + F_2 + \cdots + F_n = F_{n+2} -1. \] Then \[ \begin{eqnarray} F_0 + F_1 + F_2 + \cdots + F_n + F_{n+1} &=& ( F_0 + F_1 + F_2 + \cdots + F_n) + F_{n+1} \\ &=& ( F_{n+2} -1 ) + F_{n+1} &\qquad \text{(by assumption)}\\ &=& ( F_{n+2} + F_{n+1} ) -1 \\ &=& F_{n+3} -1, \end{eqnarray} \] which is the statement for \( n+1 \). This completes the induction. \(_\square \)
Consider the sequence of numbers given by \( b_1 = 3, b_2 = 9 \) and \( b_{n+2} = b_{n+1} + 2 \times b_n \) for all positive integers \(n\). Show that \( b_n = 2 ^ { n+1} + (-1) ^ n \).
Base case:
Let's check \( n = 1, 2 \).
LHS: \( b_1 = 3 \). RHS: \( 2 ^ 2 + (-1)^1 = 4 - 1 = 3 \).
LHS: \( b_ 2 = 9 \). RHS: \( 2^3 + (-1)^2 = 8 + 1 = 9 \).
Hence the base case is true.Induction step:
Assume that \( b_n = 2 ^{n+1} + (-1)^n \) and \( b_{n+1} = 2^{n+2} + (-1)^{n+1} \).
Then we have
\[\begin{array} {l l } b_{n+2} & = b_{n+1} + 2 \times b_n \\ & = \left(2^{n+2} + (-1)^{n+1} \right) + 2 \times \left(2 ^{n+1} + (-1)^n\right) \\ &= \left(2^{n+2} + 2^{n+2}\right) + \left( (-1)^{n+1} - 2 \times (-1)^{n+1} \right) \\ &= 2 \times 2 ^ {n+2} + (-1) \times (-1) ^ { n + 1 } \\
&= 2^{n+3} + (-1)^{n+2} \\ \end{array} \] Hence the inductive step is true and the result follows. \(_\square\)Note: Why did we do 2 bases cases? This is because in the inductive step we have to use 2 equations.
As you can see, induction is a powerful tool for us to verify an identity. However, if we were not given the closed form, it could be harder to prove the statement by induction. Instead, we will need to study linear recurrence relations in order to understand how to solve them.
Let \(b_{k,n}\) be the \(k^\text{th}\) element of the \(n^\text{th}\) row of Pascal's triangle, with row \(1\) being \(\{1\},\) row \(2\) being \(\{1,1\},\) etc. Also, the \(1^\text{st}\) element of each row is \(1.\)
Find the value of
\[(b_{3,2015})^2 - \sum_{i=1}^{2013} i^3.\]
Details and Assumptions:
- For example, \(b_{1,1} = 1, b_{2,3} = 2,\) and \(b_{5,6} = 5.\)
Image Credit: Wikipedia Pascal Triangle
Examples - Functional Equations
The following theorem is an extremely important fact in functional equations.
\(f\) is a real-valued function defined on the rationals such that \(f(a+b)=f(a)+f(b)\) for all rational values \(a\) and \(b\). Then \(f(x)=xf(1)\) for all rational values \(x\).
We provide a sketch of the proof. Details are left to the reader.
We first show by induction that \( f(na) = nf(a) \) for all positive integers \(n\).
We then show that \(f(0)=0, f(-na)=-nf(a)\), so the statement holds for all integers.
By substituting \(a=1\) and \(n=n,\) we get that \(f(n) = nf(a) \) for all integers.
We substitute \( a = \frac {m}{n}\) and \(n=n\) to get that\[ m f(1) = f(m) = n f\left(\frac {m}{n}\right) \implies f\left(\frac {m}{n}\right) = \frac {m}{n} f(1) \]
for all integers \(n\) and \(m\). \(_\square\)
Let \(f\) be a function from \(\mathbb{Z}^+\) to \(\mathbb{Z}^*\) such that
- \(f(1)=0\)
- \(f(2n)=2f(n)+1\)
- \(f(2n+1)=2f(n).\)
Find the smallest value of \(n\) such that \(f(n)=1994\).
Notation: \(\mathbb Z^+ \) denotes the set of positive integers, and \(\mathbb{Z}^*\) denotes the set of non-negative integers.
How many functions \(f(x)\) from integers to integers are there such that for all integer \(n\) we have
\[f\big(f(n)+1\big)=n?\]
Note: The main point is not really solving it, but to prove your result.
Examples - Differentiation
\[ \Large f(x;n) = \underbrace{ x^{x^{.^{.^x}}} }_{\text{number of } x \text{'s } =\ n } \]
\(\)
A positive integer \(n\) is randomly chosen between 1 and 10000 inclusive for the function described above.
If \(p\) denotes the probability that \( \displaystyle \lim_{x \to 0} f(x;n) = 1, \) what is the value of \( \left \lfloor 1000p \right \rfloor?\)
Examples - Integration
Given that
\[ { I }(n)=\int _{ 0 }^{ \frac { \pi }{ 4 } }{ \cos ^{ n }{ x } \, dx },\]
if \(I(5) = \frac { a\sqrt { b } }{ c } \), what is \(a + b + c?\)
Details and Assumptions:
- You can use \(\int { \cos { ax } } \, dx =\frac { 1 }{ a } \sin { ax } \).
- \(a, b, c\) are positive integers, \( \gcd(a,c)=1,\) and \(b\) is a square-free integer.
Which of the following is/are used in the derivation of
\[(s-1)! \equiv \int_{0}^{\infty} e^{-t}t^{s-1} \, dt\, ?\]
A.\(\ \) Integration by parts
B.\(\ \) U-substitution
C.\(\ \) Induction
Examples - Combinatorics Applications
A country has \(n\) cities. Any two cities are connected by a one-way road. Show that there is a route that passes through every city.
The statement is obviously true for \(n=1\) or \(n=2\). So we're clear in the "base-case department."
But how do we show the inductive step, that is, if we know that there is a route for a country with \(k\) cities, how do we show that a route exists for a country with \((k+1)\) cities?
Let's write down what we already know. Let's say the \(k\) cities are \(C_1, C_2, C_3,\cdots, C_{k}\) and there is a route
\[C_{1}\rightarrow C_{2} \rightarrow C_{3} \rightarrow \cdots\rightarrow C_k\]
that passes through all of them. This is our induction hypothesis. Now we have to show the inductive step. In other words, if we have another city \(C_{k+1}\), we have to show that it is possible to insert it somewhere in the route above.
We know that every two cities are connected by a one-way road. That means there is a road between \(C_k\) and \(C_{k+1}\). Can we add \(C_{k+1}\) to the end of the route like that?
No, because the roads are one-way and thus it is very much possible that the road between \(C_k\) and \(C_{k+1}\) may go the wrong way. We can't simply say that our route is
\[C_1 \rightarrow C_2 \rightarrow C_3 \rightarrow \cdots \rightarrow C_k \rightarrow C_{k+1}\]
and that we are done with it. It's a bit more complicated than that.
However, all hope is not gone. Remember that any two cities are connected by a road. There is a possibility that \(C_{k+1} \rightarrow C_1\). If that is the case, we're done because we have the route
\[ C_{k+1} \rightarrow C_1 \rightarrow C_2\rightarrow C_3 \rightarrow \cdots \rightarrow C_k.\]
If that is not the case, there exists an \(i\), with \(1\leq i\leq k,\) such that \(C_i \rightarrow C_{k+1}\).
Take the largest such \(i\). By definition, we have \(C_i\rightarrow C_{k+1}\rightarrow C_{i+1}\). Now we can insert \(C_{k+1}\) in between these two cities and we have the route
\[C_1\rightarrow C_2\rightarrow \cdots C_i\rightarrow C_{k+1}\rightarrow C_{i+1}\rightarrow \cdots \rightarrow C_k,\]
which completes our proof. \(_\square\)
Note: There's a possibility that \(C_{i+1}=C_{k+1}\). That just means that you have to take \(C_{k+1}\) to the end of the route.
For some positive integers \(n\), there exists a polynomial in \(n\) variables whose image is exactly the set of the real positive numbers (note that 0 is not included in this set). The values of \(n\) verifying that property are called Bremen numbers.
Find the sum of all the Bremen numbers smaller than or equal to 30.
Submit 0 as your answer if you believe that there does not exist any Bremen number smaller than or equal to 30.
Problem Solving
Here are some tips:
- Know when induction is a good approach. Problems containing the phrase "prove for all positive integers \(n\)" are good candidates for induction.
- Never miss the base case. Although most of the times the base case is obvious, the proof isn't complete unless you show it. Not justifying the base case leads to a lot of fallacious proofs.
- If you want to use induction in a problem, make sure you have at least some sort of idea about how you're going to link \(P(k+1)\) to \(P(k).\)
- Sometimes proving something harder is easier! See "Stronger" Induction.
- Sometimes starting with a smaller base case makes calculation easier. Sometimes starting with a larger base case makes the induction step easier. Induction can also be used on finite discrete sets.
- You do not always induct on the variable \(n.\)
- If the hypothesis is given, questions usually test your mathematical ability to manipulate values.
If the proposition is not given, it tests your ability to make sense of a series and spot any underlying pattern crucial to the solution. - Though induction can establish the truthfulness of a statement, it rarely provides the motivation/reasoning behind the problem. However, it might provide a simpler solution.
Consider an 8 by 8 square grid with 1 random tile removed. Show that the remaining area can be completely tiled with 21 L-shaped triminos.
This might seem like a strange problem for induction because there is no variable to induct on. The trick to this problem is to instead show that
\[\text{a } 2^n \times 2^n \text{ square grid with }1\text{ random tile removed can be completely tiled with L-shaped triminos}.\]
Give it a try!
Proof of Mathematical Induction
Let \(S\) be a set of positive integers with the following properties:
(1) The integer 1 belongs to the set.
(2) Whenever integer \(k\) is in \(S\), the next integer \(k+1\) must also be in \(S\).Then \(S\) is the set of all positive integers.
This statement seems almost immediately obvious. A proof is provided for completeness but is not essential in understanding induction.
We will prove this theorem by contradiction.
Let \(T\) be the set of all positive integers not in \(S\). By assumption, \(T\) is non-empty. Hence, according to the well-ordering principle, it must contain the smallest element, which we will denote by \(\alpha\).
By (1), \(0 < \alpha-1 < \alpha\). Since \( \alpha\) is the smallest integer in \(T\), this implies that \( \alpha-1 \not\in T \implies (\alpha-1)\in S \).
By (2), \(S\) must also contain \( (\alpha-1)+1=\alpha\). This contradicts the assumption that \(\alpha\in\) \(T\).Hence, set \(T\) is empty and set \(S\) contains all positive integers. \(_\square \)