definition hypothesis mathematical induction

• History & Society
• Science & Tech
• Biographies
• Animals & Nature
• Geography & Travel
• Arts & Culture
• Games & Quizzes
• On This Day
• One Good Fact
• New Articles
• Lifestyles & Social Issues
• Philosophy & Religion
• Politics, Law & Government
• World History
• Health & Medicine
• Browse Biographies
• Birds, Reptiles & Other Vertebrates
• Bugs, Mollusks & Other Invertebrates
• Environment
• Fossils & Geologic Time
• Entertainment & Pop Culture
• Sports & Recreation
• Visual Arts
• Demystified
• Image Galleries
• Infographics
• Top Questions
• Britannica Kids
• Saving Earth
• Space Next 50
• Student Center
• Introduction

Principle of mathematical induction

Proof by mathematical induction, transfinite induction.

mathematical induction

Our editors will review what you’ve submitted and determine whether to revise the article.

• Mathematics LibreTexts - Mathematical Induction - An Introduction
• Math is Fun - Mathematical Induction
• University of Hawaiʻi - Mathematical induction
• University of California, San Diego - Department of Computer Science and Engineering - Mathematical Induction
• University of Utah - Department of Mathematics - Mathematical Induction
• Wichita State University - Mathematical Induction
• Academia - Mathematical Induction and Induction in Mathematics
• Table Of Contents

mathematical induction , one of various methods of proof of mathematical propositions, based on the principle of mathematical induction .

A class of integers is called hereditary if, whenever any integer x belongs to the class, the successor of x (that is, the integer x + 1) also belongs to the class. The principle of mathematical induction is then: If the integer 0 belongs to the class F and F is hereditary, every nonnegative integer belongs to F . Alternatively, if the integer 1 belongs to the class F and F is hereditary, then every positive integer belongs to F . The principle is stated sometimes in one form, sometimes in the other. As either form of the principle is easily proved as a consequence of the other, it is not necessary to distinguish between the two.

The principle is also often stated in intensional form: A property of integers is called hereditary if, whenever any integer x has the property, its successor has the property. If the integer 1 has a certain property and this property is hereditary, every positive integer has the property.

An example of the application of mathematical induction in the simplest case is the proof that the sum of the first n odd positive integers is n 2 —that is, that (1.) 1 + 3 + 5 +⋯+ (2 n − 1) = n 2 for every positive integer n . Let F be the class of integers for which equation (1.) holds; then the integer 1 belongs to F , since 1 = 1 2 . If any integer x belongs to F , then (2.) 1 + 3 + 5 +⋯+ (2 x − 1) = x 2 . The next odd integer after 2 x − 1 is 2 x + 1, and, when this is added to both sides of equation (2.) , the result is (3.) 1 + 3 + 5 +⋯+ (2 x + 1) = x 2 + 2 x + 1 = ( x + 1) 2 . Equation (2.) is called the hypothesis of induction and states that equation (1.) holds when n is x , while equation (3.) states that equation (1.) holds when n is x + 1. Since equation (3.) has been proved as a consequence of equation (2.) , it has been proved that whenever x belongs to F the successor of x belongs to F . Hence by the principle of mathematical induction all positive integers belong to F .

The foregoing is an example of simple induction; an illustration of the many more complex kinds of mathematical induction is the following method of proof by double induction. To prove that a particular binary relation F holds among all positive integers, it is sufficient to show first that the relation F holds between 1 and 1; second that whenever F holds between x and y , it holds between x and y + 1; and third that whenever F holds between x and a certain positive integer z (which may be fixed or may be made to depend on x ), it holds between x + 1 and 1.

The logical status of the method of proof by mathematical induction is still a matter of disagreement among mathematicians. Giuseppe Peano included the principle of mathematical induction as one of his five axioms for arithmetic. Many mathematicians agree with Peano in regarding this principle just as one of the postulates characterizing a particular mathematical discipline (arithmetic) and as being in no fundamental way different from other postulates of arithmetic or of other branches of mathematics .

Henri Poincaré maintained that mathematical induction is synthetic and a priori—that is, it is not reducible to a principle of logic or demonstrable on logical grounds alone and yet is known independently of experience or observation. Thus mathematical induction has a special place as constituting mathematical reasoning par excellence and permits mathematics to proceed from its premises to genuinely new results, something that supposedly is not possible by logic alone. In this doctrine Poincaré has been followed by the school of mathematical intuitionism which treats mathematical induction as an ultimate foundation of mathematical thought, irreducible to anything prior to it and synthetic a priori in the sense of Immanuel Kant .

Directly opposed to this is the undertaking of Gottlob Frege , later followed by Alfred North Whitehead and Bertrand Russell in Principia Mathematica , to show that the principle of mathematical induction is analytic in the sense that it is reduced to a principle of pure logic by suitable definitions of the terms involved.

A generalization of mathematical induction applicable to any well-ordered class or domain D , in place of the domain of positive integers, is the method of proof by transfinite induction. The domain D is said to be well ordered if the elements (numbers or entities of any other kind) belonging to it are in, or have been put into, an order in such a way that: 1. no element precedes itself in order; 2. if x precedes y in order, and y precedes z , then x precedes z ; 3. in every non-empty subclass of D there is a first element (one that precedes all other elements in the subclass). From 3. it follows in particular that the domain D itself, if it is not empty, has a first element.

When an element x precedes an element y in the order just described, it may also be said that y follows x . The successor of an element x of a well-ordered domain D is defined as the first element that follows x (since by 3. , if there are any elements that follow x , there must be a first among them). Similarly, the successor of a class E of elements of D is the first element that follows all members of E . A class F of elements of D is called hereditary if, whenever all the members of a class E of elements of D belong to F , the successor of E , if any, also belongs to F (and hence in particular, whenever an element x of D belongs to F , the successor of x , if any, also belongs to F ). Proof by transfinite induction then depends on the principle that if the first element of a well-ordered domain D belongs to a hereditary class F , all elements of D belong to F .

One way of treating mathematical induction is to take it as a special case of transfinite induction. For example, there is a sense in which simple induction may be regarded as transfinite induction applied to the domain D of positive integers. The actual reduction of simple induction to this special case of transfinite induction requires the use of principles which themselves are ordinarily proved by mathematical induction, especially the ordering of the positive integers, and the principle that the successor of a class of positive integers, if there is one, must be the successor of a particular integer (the last or greatest integer) in the class. There is therefore also a sense in which mathematical induction is not reducible to transfinite induction.

The point of view of transfinite induction is, however, useful in classifying the more complex kinds of mathematical induction. In particular, double induction may be thought of as transfinite induction applied to the domain D of ordered pairs ( x , y ) of positive integers, where D is well ordered by the rule that the pair ( x 1 , y 1 ) precedes the pair ( x 2 , y 2 ) if x 1 < x 2 or if x 1 = x 2 and y 1 < y 2 .

Reset password New user? Sign up

Existing user? Log in

Already have an account? Log in here.

• Gerald Huang
• Hua Zhi Vee
• Aditya Raut
• Samuraiwarm Sakuraba
• Kuldeep Guha Mazumder
• shivamani patil
• Arya Samanta
• Rohit Udaiwal

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.

Formulation

Examples - summation, examples - inequalities, examples - divisibility, examples - recurrence relations, examples - functional equations, examples - differentiation, examples - integration, examples - combinatorics applications, problem solving, proof of mathematical induction.

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 .

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!

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?\)

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 .

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.

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

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(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.

\[ \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?\)

\[ { I }(n)=\int _{ 0 }^{ \frac { \pi }{ 4 } }{ \cos ^{ n }{ x } \, dx },\]

if \(I(5) = \frac { a\sqrt { b } }{ c } \), what is \(a + b + c?\)

• 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

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.

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!

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 \)

• Flawed Induction Proofs

Problem Loading...

Note Loading...

Set Loading...

• Number Theory
• Data Structures
• Cornerstones

The Principle of Mathematical Induction

If you have ever made a domino line (like the one made out of books in the video below), you are familiar with the general idea behind mathematical induction.

In order to get all of the dominoes to fall, two things need to happen:

The first domino must fall.

The dominos must be setup so that if any single domino falls, say the $k^{th}$ one in line, then we know that the next one in the line -- the $(k+1)^{th}$ one in line -- will also fall.

Suppose we are trying to prove some statement $S(n)$ is true for every positive integer $n$. For example, maybe $S(n)$ is the statement "The sum of the first $n$ positive odd numbers is $n^2$. For any given value of $n$, $S(n)$ might be trivial to verify. Certainly it is easy to check (via simple arithmetic) the aforementioned statement is true for any individual value of $n$:

However, we desire to show that this works for all positive integers $n$. We can't check every possibility via arithmetic -- there are infinitely many possibilities!

Instead, we think of each $S(n)$ as a domino that either falls or doesn't fall, according to whether $S(n)$ is true or not true, respectively.

We may then reasonably conclude that $S(n)$ is true for every positive integer $n$ (i.e., all of the dominoes fall), if we know:

$S(1)$ is true (i.e., the first domino falls); and

If $S(k)$ is true for any particular value of $k$, then $S(k+1)$ must also be true (i.e., if the $k^{th}$ domino falls, then the $(k+1)^{th}$ domino must also fall).

Formalizing the above method of argument, by removing the references to dominoes, we have:

The Principle of Mathematical Induction.

• The statement holds for $n=1$, and
• Whenever the statement holds for $n=k$, it must also hold for $n=k+1$

In an inductive argument, demonstrating the first condition above holds is called the basis step , while demonstrating the second is called the inductive step . Further, the assumption that the statement holds for $n=k$ for some particular value of $k$ that is necessary to demonstrate the inductive step is called the inductive hypothesis .

Consider the following simple example of an argument by induction involving summations:

Starting with the basis step , we must show that the statement holds for $n=1$.

Note however, when $n=1$, the left side collapses to a "sum" containing only a single term: $$\sum_{i=1}^n i = 1$$

While on the right side, if $n=1$, $$\frac{n(n+1)}{2} = \frac{1(1+1)}{2} = 1$$

Since the left and right sides agree in value, the statement is true when $n=1$

Now we proceed with the inductive step , where we must show that if we know the statement holds for some particular value of $n$, say $n=k$, then the statement must also hold when $n=k+1$.

Equivalently for this problem, we need to show if the following "inductive hypothesis" is true $$\sum_{i=1}^k i = \frac{k(k+1)}{2}$$ then it must also be true that $$\sum_{i=1}^{k+1} i = \frac{(k+1)((k+1)+1)}{2}$$

To this end, we will attempt to manipulate the left side of the above equation until it looks like the right side. We can use the inductive hypothesis to provide the transition from an expression involving $\sum$ to a simpler algebraic expression.

Having met with success in both the basis and inductive steps, we are free to conclude by the principle of mathematical induction, that the following is true for every positive integer $n$: $$\sum_{i=1}^n i = \frac{n(n+1)}{2}$$

Discrete Mathematics: An Open Introduction, 3rd edition

Oscar Levin

Search Results:

Section 2.5 induction.

Mathematical induction is a proof technique, not unlike direct proof or proof by contradiction or combinatorial proof.  3  In other words, induction is a style of argument we use to convince ourselves and others that a mathematical statement is always true. Many mathematical statements can be proved by simply explaining what they mean. Others are very difficult to prove—in fact, there are relatively simple mathematical statements which nobody yet knows how to prove. To facilitate the discovery of proofs, it is important to be familiar with some standard styles of arguments. Induction is one such style. Let's start with an example:

Subsection Stamps

Investigate.

You need to mail a package, but don't yet know how much postage you will need. You have a large supply of 8-cent stamps and 5-cent stamps. Which amounts of postage can you make exactly using these stamps? Which amounts are impossible to make?

Perhaps in investigating the problem above you picked some amounts of postage, and then figured out whether you could make that amount using just 8-cent and 5-cent stamps. Perhaps you did this in order: can you make 1 cent of postage? Can you make 2 cents? 3 cents? And so on. If this is what you did, you were actually answering a sequence of questions. We have methods for dealing with sequences. Let's see if that helps.

Actually, we will not make a sequence of questions, but rather a sequence of statements. Let \(P(n)\) be the statement “you can make \(n\) cents of postage using just 8-cent and 5-cent stamps.” Since for each value of \(n\text{,}\) \(P(n)\) is a statement, it is either true or false. So if we form the sequence of statements

the sequence will consist of \(T\) 's (for true) and \(F\) 's (for false). In our particular case the sequence starts

because \(P(1), P(2), P(3), P(4)\) are all false (you cannot make 1, 2, 3, or 4 cents of postage) but \(P(5)\) is true (use one 5-cent stamp), and so on.

Let's think a bit about how we could find the value of \(P(n)\) for some specific \(n\) (the “value” will be either \(T\) or \(F\) ). How did we find the value of the \(n\) th term of a sequence of numbers? How did we find \(a_n\text{?}\) There were two ways we could do this: either there was a closed formula for \(a_n\text{,}\) so we could plug in \(n\) into the formula and get our output value, or we had a recursive definition for the sequence, so we could use the previous terms of the sequence to compute the \(n\) th term. When dealing with sequences of statements, we could use either of these techniques as well. Maybe there is a way to use \(n\) itself to determine whether we can make \(n\) cents of postage. That would be something like a closed formula. Or instead we could use the previous terms in the sequence (of statements) to determine whether we can make \(n\) cents of postage. That is, if we know the value of \(P(n-1)\text{,}\) can we get from that to the value of \(P(n)\text{?}\) That would be something like a recursive definition for the sequence. Remember, finding recursive definitions for sequences was often easier than finding closed formulas. The same is true here.

Suppose I told you that \(P(43)\) was true (it is). Can you determine from this fact the value of \(P(44)\) (whether it true or false)? Yes you can. Even if we don't know how exactly we made 43 cents out of the 5-cent and 8-cent stamps, we do know that there was some way to do it. What if that way used at least three 5-cent stamps (making 15 cents)? We could replace those three 5-cent stamps with two 8-cent stamps (making 16 cents). The total postage has gone up by 1, so we have a way to make 44 cents, so \(P(44)\) is true. Of course, we assumed that we had at least three 5-cent stamps. What if we didn't? Then we must have at least three 8-cent stamps (making 24 cents). If we replace those three 8-cent stamps with five 5-cent stamps (making 25 cents) then again we have bumped up our total by 1 cent so we can make 44 cents, so \(P(44)\) is true.

Notice that we have not said how to make 44 cents, just that we can, on the basis that we can make 43 cents. How do we know we can make 43 cents? Perhaps because we know we can make \(42\) cents, which we know we can do because we know we can make 41 cents, and so on. It's a recursion! As with a recursive definition of a numerical sequence, we must specify our initial value. In this case, the initial value is “ \(P(1)\) is false.” That's not good, since our recurrence relation just says that \(P(k+1)\) is true if \(P(k)\) is also true. We need to start the process with a true \(P(k)\text{.}\) So instead, we might want to use “ \(P(28)\) is true” as the initial condition.

Putting this all together we arrive at the following fact: it is possible to (exactly) make any amount of postage greater than 27 cents using just 5-cent and 8-cent stamps.  4  In other words, \(P(k)\) is true for any \(k \ge 28\text{.}\) To prove this, we could do the following:

Demonstrate that \(P(28)\) is true.

Prove that if \(P(k)\) is true, then \(P(k+1)\) is true (for any \(k \ge 28\) ).

Suppose we have done this. Then we know that the 28th term of the sequence above is a \(T\) (using step 1, the initial condition or base case ), and that every term after the 28th is \(T\) also (using step 2, the recursive part or inductive case ). Here is what the proof would actually look like.

Let \(P(n)\) be the statement “it is possible to make exactly \(n\) cents of postage using 5-cent and 8-cent stamps.” We will show \(P(n)\) is true for all \(n \ge 28\text{.}\)

First, we show that \(P(28)\) is true: \(28 = 4 \cdot 5+ 1\cdot 8\text{,}\) so we can make \(28\) cents using four 5-cent stamps and one 8-cent stamp.

Now suppose \(P(k)\) is true for some arbitrary \(k \ge 28\text{.}\) Then it is possible to make \(k\) cents using 5-cent and 8-cent stamps. Note that since \(k \ge 28\text{,}\) it cannot be that we use fewer than three 5-cent stamps and fewer than three 8-cent stamps: using two of each would give only 26 cents. Now if we have made \(k\) cents using at least three 5-cent stamps, replace three 5-cent stamps by two 8-cent stamps. This replaces 15 cents of postage with 16 cents, moving from a total of \(k\) cents to \(k+1\) cents. Thus \(P(k+1)\) is true. On the other hand, if we have made \(k\) cents using at least three 8-cent stamps, then we can replace three 8-cent stamps with five 5-cent stamps, moving from 24 cents to 25 cents, giving a total of \(k+1\) cents of postage. So in this case as well \(P(k+1)\) is true.

Therefore, by the principle of mathematical induction, \(P(n)\) is true for all \(n \ge 28\text{.}\)

Subsection Formalizing Proofs

What we did in the stamp example above works for many types of problems. Proof by induction is useful when trying to prove statements about all natural numbers, or all natural numbers greater than some fixed first case (like 28 in the example above), and in some other situations too. In particular, induction should be used when there is some way to go from one case to the next – when you can see how to always “do one more.”

This is a big idea. Thinking about a problem inductively can give new insight into the problem. For example, to really understand the stamp problem, you should think about how any amount of postage (greater than 28 cents) can be made (this is non-inductive reasoning) and also how the ways in which postage can be made changes as the amount increases (inductive reasoning). When you are asked to provide a proof by induction, you are being asked to think about the problem dynamically ; how does increasing \(n\) change the problem?

But there is another side to proofs by induction as well. In mathematics, it is not enough to understand a problem, you must also be able to communicate the problem to others. Like any discipline, mathematics has standard language and style, allowing mathematicians to share their ideas efficiently. Proofs by induction have a certain formal style, and being able to write in this style is important. It allows us to keep our ideas organized and might even help us with formulating a proof.

Here is the general structure of a proof by mathematical induction:

Induction Proof Structure.

Start by saying what the statement is that you want to prove: “Let \(P(n)\) be the statement…” To prove that \(P(n)\) is true for all \(n \ge 0\text{,}\) you must prove two facts:

Base case: Prove that \(P(0)\) is true. You do this directly. This is often easy.

Inductive case: Prove that \(P(k) \imp P(k+1)\) for all \(k \ge 0\text{.}\) That is, prove that for any \(k \ge 0\) if \(P(k)\) is true, then \(P(k+1)\) is true as well. This is the proof of an if … then … statement, so you can assume \(P(k)\) is true ( \(P(k)\) is called the inductive hypothesis ). You must then explain why \(P(k+1)\) is also true, given that assumption.

Assuming you are successful on both parts above, you can conclude, “Therefore by the principle of mathematical induction, the statement \(P(n)\) is true for all \(n \ge 0\text{.}\) ”

Sometimes the statement \(P(n)\) will only be true for values of \(n \ge 4\text{,}\) for example, or some other value. In such cases, replace all the 0's above with 4's (or the other value).

The other advantage of formalizing inductive proofs is it allows us to verify that the logic behind this style of argument is valid. Why does induction work? Think of a row of dominoes set up standing on their edges. We want to argue that in a minute, all the dominoes will have fallen down. For this to happen, you will need to push the first domino. That is the base case. It will also have to be that the dominoes are close enough together that when any particular domino falls, it will cause the next domino to fall. That is the inductive case. If both of these conditions are met, you push the first domino over and each domino will cause the next to fall, then all the dominoes will fall.

Induction is powerful! Think how much easier it is to knock over dominoes when you don't have to push over each domino yourself. You just start the chain reaction, and the rely on the relative nearness of the dominoes to take care of the rest.

Think about our study of sequences. It is easier to find recursive definitions for sequences than closed formulas. Going from one case to the next is easier than going directly to a particular case. That is what is so great about induction. Instead of going directly to the (arbitrary) case for \(n\text{,}\) we just need to say how to get from one case to the next.

When you are asked to prove a statement by mathematical induction, you should first think about why the statement is true, using inductive reasoning. Explain why induction is the right thing to do, and roughly why the inductive case will work. Then, sit down and write out a careful, formal proof using the structure above.

Subsection Examples

Here are some examples of proof by mathematical induction.

Example 2.5.1 .

Prove for each natural number \(n \ge 1\) that \(1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}\text{.}\)

First, let's think inductively about this equation. In fact, we know this is true for other reasons (reverse and add comes to mind). But why might induction be applicable? The left-hand side adds up the numbers from 1 to \(n\text{.}\) If we know how to do that, adding just one more term ( \(n+1\) ) would not be that hard. For example, if \(n = 100\text{,}\) suppose we know that the sum of the first 100 numbers is \(5050\) (so \(1 + 2 + 3 + \cdots + 100 = 5050\text{,}\) which is true). Now to find the sum of the first 101 numbers, it makes more sense to just add 101 to 5050, instead of computing the entire sum again. We would have \(1 + 2 + 3 + \cdots + 100 + 101 = 5050 + 101 = 5151\text{.}\) In fact, it would always be easy to add just one more term. This is why we should use induction.

Now the formal proof:

Let \(P(n)\) be the statement \(1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}\text{.}\) We will show that \(P(n)\) is true for all natural numbers \(n \ge 1\text{.}\)

Base case: \(P(1)\) is the statement \(1 = \frac{1(1+1)}{2}\) which is clearly true.

Inductive case: Let \(k \ge 1\) be a natural number. Assume (for induction) that \(P(k)\) is true. That means \(1 + 2 + 3 + \cdots + k = \frac{k(k+1)}{2}\text{.}\) We will prove that \(P(k+1)\) is true as well. That is, we must prove that \(1 + 2 + 3 + \cdots + k + (k+1) = \frac{(k+1)(k+2)}{2}\text{.}\) To prove this equation, start by adding \(k+1\) to both sides of the inductive hypothesis:

Now, simplifying the right side we get:

Thus \(P(k+1)\) is true, so by the principle of mathematical induction \(P(n)\) is true for all natural numbers \(n \ge 1\text{.}\)

Note that in the part of the proof in which we proved \(P(k+1)\) from \(P(k)\text{,}\) we used the equation \(P(k)\text{.}\) This was the inductive hypothesis. Seeing how to use the inductive hypotheses is usually straight forward when proving a fact about a sum like this. In other proofs, it can be less obvious where it fits in.

Example 2.5.2 .

Prove that for all \(n \in \N\text{,}\) \(6^n - 1\) is a multiple of 5.

Again, start by understanding the dynamics of the problem. What does increasing \(n\) do? Let's try with a few examples. If \(n = 1\text{,}\) then yes, \(6^1 - 1 = 5\) is a multiple of 5. What does incrementing \(n\) to 2 look like? We get \(6^2 - 1 = 35\text{,}\) which again is a multiple of 5. Next, \(n = 3\text{:}\) but instead of just finding \(6^3 - 1\text{,}\) what did the increase in \(n\) do? We will still subtract 1, but now we are multiplying by another 6 first. Viewed another way, we are multiplying a number which is one more than a multiple of 5 by 6 (because \(6^2 - 1\) is a multiple of 5, so \(6^2\) is one more than a multiple of 5). What do numbers which are one more than a multiple of 5 look like? They must have last digit 1 or 6. What happens when you multiply such a number by 6? Depends on the number, but in any case, the last digit of the new number must be a 6. And then if you subtract 1, you get last digit 5, so a multiple of 5.

The point is, every time we multiply by just one more six, we still get a number with last digit 6, so subtracting 1 gives us a multiple of 5. Now the formal proof:

Let \(P(n)\) be the statement, “ \(6^n - 1\) is a multiple of 5.” We will prove that \(P(n)\) is true for all \(n \in \N\text{.}\)

Base case: \(P(0)\) is true: \(6^0 -1 = 0\) which is a multiple of 5.

Inductive case: Let \(k\) be an arbitrary natural number. Assume, for induction, that \(P(k)\) is true. That is, \(6^k - 1\) is a multiple of \(5\text{.}\) Then \(6^k - 1 = 5j\) for some integer \(j\text{.}\) This means that \(6^k = 5j + 1\text{.}\) Multiply both sides by \(6\text{:}\)

But we want to know about \(6^{k+1} - 1\text{,}\) so subtract 1 from both sides:

Of course \(30j+5 = 5(6j+1)\text{,}\) so is a multiple of 5.

Therefore \(6^{k+1} - 1\) is a multiple of 5, or in other words, \(P(k+1)\) is true. Thus, by the principle of mathematical induction \(P(n)\) is true for all \(n \in \N\text{.}\)

We had to be a little bit clever (i.e., use some algebra) to locate the \(6^k - 1\) inside of \(6^{k+1} - 1\) before we could apply the inductive hypothesis. This is what can make inductive proofs challenging.

In the two examples above, we started with \(n = 1\) or \(n = 0\text{.}\) We can start later if we need to.

Example 2.5.3 .

Prove that \(n^2 \lt 2^n\) for all integers \(n \ge 5\text{.}\)

First, the idea of the argument. What happens when we increase \(n\) by 1? On the left-hand side, we increase the base of the square and go to the next square number. On the right-hand side, we increase the power of 2. This means we double the number. So the question is, how does doubling a number relate to increasing to the next square? Think about what the difference of two consecutive squares looks like. We have \((n+1)^2 - n^2\text{.}\) This factors:

But doubling the right-hand side increases it by \(2^n\text{,}\) since \(2^{n+1} = 2^n + 2^n\text{.}\) When \(n\) is large enough, \(2^n > 2n + 1\text{.}\)

What we are saying here is that each time \(n\) increases, the left-hand side grows by less than the right-hand side. So if the left-hand side starts smaller (as it does when \(n = 5\) ), it will never catch up. Now the formal proof:

Let \(P(n)\) be the statement \(n^2 \lt 2^n\text{.}\) We will prove \(P(n)\) is true for all integers \(n \ge 5\text{.}\)

Base case: \(P(5)\) is the statement \(5^2 \lt 2^5\text{.}\) Since \(5^2 = 25\) and \(2^5 = 32\text{,}\) we see that \(P(5)\) is indeed true.

Inductive case: Let \(k \ge 5\) be an arbitrary integer. Assume, for induction, that \(P(k)\) is true. That is, assume \(k^2 \lt 2^k\text{.}\) We will prove that \(P(k+1)\) is true, i.e., \((k+1)^2 \lt 2^{k+1}\text{.}\) To prove such an inequality, start with the left-hand side and work towards the right-hand side:

Following the equalities and inequalities through, we get \((k+1)^2 \lt 2^{k+1}\text{,}\) in other words, \(P(k+1)\text{.}\) Therefore by the principle of mathematical induction, \(P(n)\) is true for all \(n \ge 5\text{.}\)

The previous example might remind you of the racetrack principle from calculus, which says that if \(f(a) \lt g(a)\text{,}\) and \(f'(x) \lt g'(x)\) for \(x > a\text{,}\) then \(f(x) \lt g(x)\) for \(x > a\text{.}\) Same idea: the larger function is increasing at a faster rate than the smaller function, so the larger function will stay larger. In discrete math, we don't have derivatives, so we look at differences. Thus induction is the way to go.

With great power, comes great responsibility. Induction isn't magic. It seems very powerful to be able to assume \(P(k)\) is true. After all, we are trying to prove \(P(n)\) is true and the only difference is in the variable: \(k\) vs. \(n\text{.}\) Are we assuming that what we want to prove is true? Not really. We assume \(P(k)\) is true only for the sake of proving that \(P(k+1)\) is true.

Still you might start to believe that you can prove anything with induction. Consider this incorrect “proof” that every Canadian has the same eye color: Let \(P(n)\) be the statement that any \(n\) Canadians have the same eye color. \(P(1)\) is true, since everyone has the same eye color as themselves. Now assume \(P(k)\) is true. That is, assume that in any group of \(k\) Canadians, everyone has the same eye color. Now consider an arbitrary group of \(k+1\) Canadians. The first \(k\) of these must all have the same eye color, since \(P(k)\) is true. Also, the last \(k\) of these must have the same eye color, since \(P(k)\) is true. So in fact, everyone the group must have the same eye color. Thus \(P(k+1)\) is true. So by the principle of mathematical induction, \(P(n)\) is true for all \(n\text{.}\)

Clearly something went wrong. The problem is that the proof that \(P(k)\) implies \(P(k+1)\) assumes that \(k \ge 2\text{.}\) We have only shown \(P(1)\) is true. In fact, \(P(2)\) is false.

Subsection Strong Induction

Start with a square piece of paper. You want to cut this square into smaller squares, leaving no waste (every piece of paper you end up with must be a square). Obviously it is possible to cut the square into 4 squares. You can also cut it into 9 squares. It turns out you can cut the square into 7 squares (although not all the same size). What other numbers of squares could you end up with?

Sometimes, to prove that \(P(k+1)\) is true, it would be helpful to know that \(P(k)\) and \(P(k-1)\) and \(P(k-2)\) are all true. Consider the following puzzle:

You have a rectangular chocolate bar, made up of \(n\) identical squares of chocolate. You can take such a bar and break it along any row or column. How many times will you have to break the bar to reduce it to \(n\) single chocolate squares?

At first, this question might seem impossible. Perhaps I meant to ask for the smallest number of breaks needed? Let's investigate.

Start with some small cases. If \(n=2\text{,}\) you must have a \(1\times 2\) rectangle, which can be reduced to single pieces in one break. With \(n=3\text{,}\) we must have a \(1\times 3\) bar, which requires two breaks: the first break creates a single square and a \(1\times 2\) bar, which we know takes one (more) break.

What about \(n=4\text{?}\) Now we could have a \(2\times 2\) bar, or a \(1 \times 4\) bar. In the first case, break the bar into two \(2\times 2\) bars, each which require one more break (that's a total of three breaks required). If we started with a \(1 \times 4\) bar, we have choices for our first break. We could break the bar in half, creating two \(1\times 2\) bars, or we could break off a single square, leaving a \(1\times 3\) bar. But either way, we still need two more breaks, giving a total of three.

It is starting to look like no matter how we break the bar (and no matter how the \(n\) squares are arranged into a rectangle), we will always have the same number of breaks required. It also looks like that number is one less than \(n\text{:}\)

Conjecture 2.5.4 .

Given a \(n\) -square rectangular chocolate bar, it always takes \(n-1\) breaks to reduce the bar to single squares.

It makes sense to prove this by induction because after breaking the bar once, you are left with smaller chocolate bars. Reducing to smaller cases is what induction is all about. We can inductively assume we already know how to deal with these smaller bars. The problem is, if we are trying to prove the inductive case about a \((k+1)\) -square bar, we don't know that after the first break the remaining bar will have \(k\) squares. So we really need to assume that our conjecture is true for all cases less than \(k+1\text{.}\)

Is it valid to make this stronger assumption? Remember, in induction we are attempting to prove that \(P(n)\) is true for all \(n\text{.}\) What if that were not the case? Then there would be some first \(n_0\) for which \(P(n_0)\) was false. Since \(n_0\) is the first counterexample, we know that \(P(n)\) is true for all \(n \lt n_0\text{.}\) Now we proceed to prove that \(P(n_0)\) is actually true, based on the assumption that \(P(n)\) is true for all smaller \(n\text{.}\)

This is quite an advantage: we now have a stronger inductive hypothesis. We can assume that \(P(1)\text{,}\) \(P(2)\text{,}\) \(P(3)\text{,}\) … \(P(k)\) is true, just to show that \(P(k+1)\) is true. Previously, we just assumed \(P(k)\) for this purpose.

It is slightly easier if we change our variables for strong induction. Here is what the formal proof would look like:

Strong Induction Proof Structure.

Again, start by saying what you want to prove: “Let \(P(n)\) be the statement…” Then establish two facts:

Base case: Prove that \(P(0)\) is true.

Inductive case: Assume \(P(k)\) is true for all \(k \lt n\text{.}\) Prove that \(P(n)\) is true.

Conclude, “therefore, by strong induction, \(P(n)\) is true for all \(n \gt 0\text{.}\) ”

Of course, it is acceptable to replace 0 with a larger base case if needed.  5 

Let's prove our conjecture about the chocolate bar puzzle:

Let \(P(n)\) be the statement, “it takes \(n-1\) breaks to reduce a \(n\) -square chocolate bar to single squares.”

Base case: Consider \(P(2)\text{.}\) The squares must be arranged into a \(1\times 2\) rectangle, and we require \(2-1 = 1\) breaks to reduce this to single squares.

Inductive case: Fix an arbitrary \(n\ge 2\) and assume \(P(k)\) is true for all \(k \lt n\text{.}\) Consider a \(n\) -square rectangular chocolate bar. Break the bar once along any row or column. This results in two chocolate bars, say of sizes \(a\) and \(b\text{.}\) That is, we have an \(a\) -square rectangular chocolate bar, a \(b\) -square rectangular chocolate bar, and \(a+b = n\text{.}\)

We also know that \(a \lt n\) and \(b \lt n\text{,}\) so by our inductive hypothesis, \(P(a)\) and \(P(b)\) are true. To reduce the \(a\) -square bar to single squares takes \(a-1\) breaks; to reduce the \(b\) -square bar to single squares takes \(b-1\) breaks. Doing this results in our original bar being reduced to single squares. All together it took the initial break, plus the \(a-1\) and \(b-1\) breaks, for a total of \(1+a-1+b-1 = a+b-1 = n-1\) breaks. Thus \(P(n)\) is true.

Therefore, by strong induction, \(P(n)\) is true for all \(n \ge 2\text{.}\)

Here is a more mathematically relevant example:

Example 2.5.5 .

Prove that any natural number greater than 1 is either prime or can be written as the product of primes.

First, the idea: if we take some number \(n\text{,}\) maybe it is prime. If so, we are done. If not, then it is composite, so it is the product of two smaller numbers. Each of these factors is smaller than \(n\) (but at least 2), so we can repeat the argument with these numbers. We have reduced to a smaller case.

Let \(P(n)\) be the statement, “ \(n\) is either prime or can be written as the product of primes.” We will prove \(P(n)\) is true for all \(n \ge 2\text{.}\)

Base case: \(P(2)\) is true because \(2\) is indeed prime.

Inductive case: assume \(P(k)\) is true for all \(k \lt n\text{.}\) We want to show that \(P(n)\) is true. That is, we want to show that \(n\) is either prime or is the product of primes. If \(n\) is prime, we are done. If not, then \(n\) has more than 2 divisors, so we can write \(n = m_1 \cdot m_2\text{,}\) with \(m_1\) and \(m_2\) less than \(n\) (and greater than 1). By the inductive hypothesis, \(m_1\) and \(m_2\) are each either prime or can be written as the product of primes. In either case, we have that \(n\) is written as the product of primes.

Thus by the strong induction, \(P(n)\) is true for all \(n \ge 2\text{.}\)

Whether you use regular induction or strong induction depends on the statement you want to prove. If you wanted to be safe, you could always use strong induction. It really is stronger , so can accomplish everything “weak” induction can. That said, using regular induction is often easier since there is only one place you can use the induction hypothesis. There is also something to be said for elegance in proofs. If you can prove a statement using simpler tools, it is nice to do so.

As a final contrast between the two forms of induction, consider once more the stamp problem. Regular induction worked by showing how to increase postage by one cent (either replacing three 5-cent stamps with two 8-cent stamps, or three 8-cent stamps with five 5-cent stamps). We could give a slightly different proof using strong induction. First, we could show five base cases: it is possible to make 28, 29, 30, 31, and 32 cents (we would actually say how each of these is made). Now assume that it is possible to make \(k\) cents of postage for all \(k \lt n\) as long as \(k \ge 28\text{.}\) As long as \(n > 32\text{,}\) this means in particular we can make \(k = n-5\) cents. Now add a 5-cent stamp to get make \(n\) cents.

Exercises Exercises

On the way to the market, you exchange your cow for some magic dark chocolate espresso beans. These beans have the property that every night at midnight, each bean splits into two, effectively doubling your collection. You decide to take advantage of this and each morning (around 8am) you eat 5 beans.

Explain why it is true that if at noon on day \(n\) you have a number of beans ending in a 5, then at noon on day \(n+1\) you will still have a number of beans ending in a 5.

Why is the previous fact not enough to conclude that you will always have a number of beans ending in a 5? What additional fact would you need?

Assuming you have the additional fact in part (b), and have successfully proved the fact in part (a), how do you know that you will always have a number of beans ending in a 5? Illustrate what is going on by carefully explaining how the two facts above prove that you will have a number of beans ending in a 5 on day 4 specifically. In other words, explain why induction works in this context.

If we have a number of beans ending in a 5 and we double it, we will get a number of beans ending in a 0 (since \(5\cdot 2 = 10\) ). Then if we subtract 5, we will once again get a number of beans ending in a 5. Thus if on any day we have a number ending in a 5, the next day will also have a number ending in a 5.

If you don't start with a number of beans ending in a 5 (on day 1), the above reasoning is still correct but not helpful. For example, if you start with a number ending in a 3, the next day you will have a number ending in a 1.

Part (b) is the base case and part (a) is the inductive case. If on day 1 we have a number ending in a 5 (by part (b)), then on day 2 we will also have a number ending in a 5 (by part (a)). Then by part (a) again, we will have a number ending in a 5 on day 3. By part (a) again, this means we will have a number ending in a 5 on day 4

The proof by induction would say that on every day we will have a number ending in a 5, and this works because we can start with the base case, then use the inductive case over and over until we get up to our desired \(n\text{.}\)

Use induction to prove for all \(n \in \N\) that \(\d\sum_{k=0}^n 2^k = 2^{n+1} - 1\text{.}\)

We must prove that \(1 + 2 + 2^2 + 2^3 + \cdots +2^n = 2^{n+1} - 1\) for all \(n \in \N\text{.}\) Thus let \(P(n)\) be the statement \(1 + 2 + 2^2 + \cdots + 2^n = 2^{n+1} - 1\text{.}\) We will prove that \(P(n)\) is true for all \(n \in \N\text{.}\) First we establish the base case, \(P(0)\text{,}\) which claims that \(1 = 2^{0+1} -1\text{.}\) Since \(2^1 - 1 = 2 - 1 = 1\text{,}\) we see that \(P(0)\) is true. Now for the inductive case. Assume that \(P(k)\) is true for an arbitrary \(k \in \N\text{.}\) That is, \(1 + 2 + 2^2 + \cdots + 2^k = 2^{k+1} - 1\text{.}\) We must show that \(P(k+1)\) is true (i.e., that \(1 + 2 + 2^2 + \cdots + 2^{k+1} = 2^{k+2} - 1\) ). To do this, we start with the left-hand side of \(P(k+1)\) and work to the right-hand side:

Thus \(P(k+1)\) is true so by the principle of mathematical induction, \(P(n)\) is true for all \(n \in \N\text{.}\)

Prove that \(7^n - 1\) is a multiple of 6 for all \(n \in \N\text{.}\)

Let \(P(n)\) be the statement “ \(7^n - 1\) is a multiple of 6.” We will show \(P(n)\) is true for all \(n \in \N\text{.}\) First we establish the base case, \(P(0)\text{.}\) Since \(7^0 - 1 = 0\text{,}\) and \(0\) is a multiple of 6, \(P(0)\) is true. Now for the inductive case. Assume \(P(k)\) holds for an arbitrary \(k \in \N\text{.}\) That is, \(7^k - 1\) is a multiple of 6, or in other words, \(7^k - 1 = 6j\) for some integer \(j\text{.}\) Now consider \(7^{k+1} - 1\text{:}\)

Therefore \(7^{k+1} - 1\) is a multiple of 6, or in other words, \(P(k+1)\) is true. Therefore by the principle of mathematical induction, \(P(n)\) is true for all \(n \in \N\text{.}\)

Prove that \(1 + 3 + 5 + \cdots + (2n-1) = n^2\) for all \(n \ge 1\text{.}\)

Let \(P(n)\) be the statement \(1+3 +5 + \cdots + (2n-1) = n^2\text{.}\) We will prove that \(P(n)\) is true for all \(n \ge 1\text{.}\) First the base case, \(P(1)\text{.}\) We have \(1 = 1^2\) which is true, so \(P(1)\) is established. Now the inductive case. Assume that \(P(k)\) is true for some fixed arbitrary \(k \ge 1\text{.}\) That is, \(1 + 3 + 5 + \cdots + (2k-1) = k^2\text{.}\) We will now prove that \(P(k+1)\) is also true (i.e., that \(1 + 3 + 5 + \cdots + (2k+1) = (k+1)^2\) ). We start with the left-hand side of \(P(k+1)\) and work to the right-hand side:

Thus \(P(k+1)\) holds, so by the principle of mathematical induction, \(P(n)\) is true for all \(n \ge 1\text{.}\)

Prove that \(F_0 + F_2 + F_4 + \cdots + F_{2n} = F_{2n+1} - 1\) where \(F_n\) is the \(n\) th Fibonacci number.

Let \(P(n)\) be the statement \(F_0 + F_2 + F_4 + \cdots + F_{2n} = F_{2n+1} - 1\text{.}\) We will show that \(P(n)\) is true for all \(n \ge 0\text{.}\) First the base case is easy because \(F_0 = 0\) and \(F_1 = 1\) so \(F_0 = F_1 - 1\text{.}\) Now consider the inductive case. Assume \(P(k)\) is true, that is, assume \(F_0 + F_2 + F_4 + \cdots + F_{2k} = F_{2k+1} - 1\text{.}\) To establish \(P(k+1)\) we work from left to right:

Therefore \(F_0 + F_2 + F_4 + \cdots + F_{2k+2} = F_{2k+3} - 1\text{,}\) which is to say \(P(k+1)\) holds. Therefore by the principle of mathematical induction, \(P(n)\) is true for all \(n \ge 0\text{.}\)

Prove that \(2^n \lt n!\) for all \(n \ge 4\text{.}\) (Recall, \(n! = 1\cdot 2 \cdot 3 \cdot \cdots\cdot n\text{.}\) )

Let \(P(n)\) be the statement \(2^n \lt n!\text{.}\) We will show \(P(n)\) is true for all \(n \ge 4\text{.}\) First, we check the base case and see that yes, \(2^4 \lt 4!\) (as \(16 \lt 24\) ) so \(P(4)\) is true. Now for the inductive case. Assume \(P(k)\) is true for an arbitrary \(k \ge 4\text{.}\) That is, \(2^k \lt k!\text{.}\) Now consider \(P(k+1)\text{:}\) \(2^{k+1} \lt (k+1)!\text{.}\) To prove this, we start with the left side and work to the right side.

Therefore \(2^{k+1} \lt (k+1)!\) so we have established \(P(k+1)\text{.}\) Thus by the principle of mathematical induction \(P(n)\) is true for all \(n \ge 4\text{.}\)

Prove, by mathematical induction, that \(F_0 + F_1 + F_2 + \cdots + F_{n} = F_{n+2} - 1\text{,}\) where \(F_n\) is the \(n\) th Fibonacci number ( \(F_0 = 0\text{,}\) \(F_1 = 1\) and \(F_n = F_{n-1} + F_{n-2}\) ).

Zombie Euler and Zombie Cauchy, two famous zombie mathematicians, have just signed up for Twitter accounts. After one day, Zombie Cauchy has more followers than Zombie Euler. Each day after that, the number of new followers of Zombie Cauchy is exactly the same as the number of new followers of Zombie Euler (and neither lose any followers). Explain how a proof by mathematical induction can show that on every day after the first day, Zombie Cauchy will have more followers than Zombie Euler. That is, explain what the base case and inductive case are, and why they together prove that Zombie Cauchy will have more followers on the 4th day.

Find the largest number of points which a football team cannot get exactly using just 3-point field goals and 7-point touchdowns (ignore the possibilities of safeties, missed extra points, and two point conversions). Prove your answer is correct by mathematical induction.

It is not possible to score exactly 11 points. Can you prove that you can score \(n\) points for any \(n \ge 12\text{?}\)

Prove that the sum of \(n\) squares can be found as follows

Prove that the sum of the interior angles of a convex \(n\) -gon is \((n-2)\cdot 180^\circ\text{.}\) (A convex \(n\) -gon is a polygon with \(n\) sides for which each interior angle is less than \(180^\circ\text{.}\) )

Start with \((k+1)\) -gon and divide it up into a \(k\) -gon and a triangle.

What is wrong with the following “proof” of the “fact” that \(n+3 = n+7\) for all values of \(n\) (besides of course that the thing it is claiming to prove is false)?

Let \(P(n)\) be the statement that \(n + 3 = n + 7\text{.}\) We will prove that \(P(n)\) is true for all \(n \in \N\text{.}\) Assume, for induction that \(P(k)\) is true. That is, \(k+3 = k+7\text{.}\) We must show that \(P(k+1)\) is true. Now since \(k + 3 = k + 7\text{,}\) add 1 to both sides. This gives \(k + 3 + 1 = k + 7 + 1\text{.}\) Regrouping \((k+1) + 3 = (k+1) + 7\text{.}\) But this is simply \(P(k+1)\text{.}\) Thus by the principle of mathematical induction \(P(n)\) is true for all \(n \in \N\text{.}\)

The only problem is that we never established the base case. Of course, when \(n = 0\text{,}\) \(0+3 \ne 0+7\text{.}\)

The proof in the previous problem does not work. But if we modify the “fact,” we can get a working proof. Prove that \(n + 3 \lt n + 7\) for all values of \(n \in \N\text{.}\) You can do this proof with algebra (without induction), but the goal of this exercise is to write out a valid induction proof.

Let \(P(n)\) be the statement that \(n + 3 \lt n + 7\text{.}\) We will prove that \(P(n)\) is true for all \(n \in \N\text{.}\) First, note that the base case holds: \(0+3 \lt 0+7\text{.}\) Now assume for induction that \(P(k)\) is true. That is, \(k+3 \lt k+7\text{.}\) We must show that \(P(k+1)\) is true. Now since \(k + 3 \lt k + 7\text{,}\) add 1 to both sides. This gives \(k + 3 + 1 \lt k + 7 + 1\text{.}\) Regrouping \((k+1) + 3 \lt (k+1) + 7\text{.}\) But this is simply \(P(k+1)\text{.}\) Thus by the principle of mathematical induction \(P(n)\) is true for all \(n \in \N\text{.}\)

Find the flaw in the following “proof” of the “fact” that \(n \lt 100\) for every \(n \in \N\text{.}\)

Let \(P(n)\) be the statement \(n \lt 100\text{.}\) We will prove \(P(n)\) is true for all \(n \in \N\text{.}\) First we establish the base case: when \(n = 0\text{,}\) \(P(n)\) is true, because \(0 \lt 100\text{.}\) Now for the inductive step, assume \(P(k)\) is true. That is, \(k \lt 100\text{.}\) Now if \(k \lt 100\text{,}\) then \(k\) is some number, like 80. Of course \(80+1 = 81\) which is still less than 100. So \(k +1 \lt 100\) as well. But this is what \(P(k+1)\) claims, so we have shown that \(P(k) \imp P(k+1)\text{.}\) Thus by the principle of mathematical induction, \(P(n)\) is true for all \(n \in \N\text{.}\)

The problem here is that while \(P(0)\) is true, and while \(P(k) \imp P(k+1)\) for some values of \(k\text{,}\) there is at least one value of \(k\) (namely \(k = 99\) ) when that implication fails. For a valid proof by induction, \(P(k) \imp P(k+1)\) must be true for all values of \(k\) greater than or equal to the base case.

While the above proof does not work (it better not since the statement it is trying to prove is false!) we can prove something similar. Prove that there is a strictly increasing sequence \(a_1, a_2, a_3, \ldots\) of numbers (not necessarily integers) such that \(a_n \lt 100\) for all \(n \in \N\text{.}\) (By strictly increasing we mean \(a_n \lt a_{n+1}\) for all \(n\text{.}\) So each term must be larger than the last.)

For the inductive step, you can assume you have a strictly increasing sequence up to \(a_k\) where \(a_k \lt 100\text{.}\) Now you just need to find the next term \(a_{k+1}\) so that \(a_{k} \lt a_{k+1} \lt 100\text{.}\) What should \(a_{k+1}\) be?

What is wrong with the following “proof” of the “fact” that for all \(n \in \N\text{,}\) the number \(n^2 + n\) is odd?

Let \(P(n)\) be the statement “ \(n^2 + n\) is odd.” We will prove that \(P(n)\) is true for all \(n \in \N\text{.}\) Suppose for induction that \(P(k)\) is true, that is, that \(k^2 + k\) is odd. Now consider the statement \(P(k+1)\text{.}\) Now \((k+1)^2 + (k+1) = k^2 + 2k + 1 + k + 1 = k^2 + k + 2k + 2\text{.}\) By the inductive hypothesis, \(k^2 + k\) is odd, and of course \(2k + 2\) is even. An odd plus an even is always odd, so therefore \((k+1)^2 + (k+1)\) is odd. Therefore by the principle of mathematical induction, \(P(n)\) is true for all \(n \in \N\text{.}\)

We once again failed to establish the base case: when \(n = 0\text{,}\) \(n^2 + n = 0\) which is even, not odd.

Now give a valid proof (by induction, even though you might be able to do so without using induction) of the statement, “for all \(n \in \N\text{,}\) the number \(n^2 + n\) is even.”

For the inductive case, you will need to show that \((k+1)^2 + (k+1)\) is even. Factor this out and locate the part of it that is \(k^2 + k\text{.}\) What have you assumed about that quantity?

Prove that there is a sequence of positive real numbers \(a_0, a_1, a_2, \ldots\) such that the partial sum \(a_0 + a_1 + a_2 + \cdots + a_n\) is strictly less than \(2\) for all \(n \in \N\text{.}\) Hint: think about how you could define what \(a_{k+1}\) is to make the induction argument work.

This is similar to Exercise 2.5.15 , although there you were showing that a sequence had all its terms less than some value, and here you are showing that the sum is less than some value. But the partial sums forms a sequence, so this is actually very similar.

Prove that every positive integer is either a power of 2, or can be written as the sum of distinct powers of 2.

The proof will be by strong induction.

Let \(P(n)\) be the statement “ \(n\) is either a power of 2 or can be written as the sum of distinct powers of 2.” We will show that \(P(n)\) is true for all \(n \ge 1\text{.}\)

Base case: \(1 = 2^0\) is a power of 2, so \(P(1)\) is true.

Inductive case: Suppose \(P(k)\) is true for all \(k \lt n\text{.}\) Now if \(n\) is a power of 2, we are done. If not, let \(2^x\) be the largest power of 2 strictly less than \(n\text{.}\) Consider \(n - 2^x\text{,}\) which is a smaller number, in fact smaller than both \(n\) and \(2^x\text{.}\) Thus \(n-2^x\) is either a power of 2 or can be written as the sum of distinct powers of 2, but none of them are going to be \(2^x\text{,}\) so the together with \(2^x\) we have written \(n\) as the sum of distinct powers of 2.

Therefore, by the principle of (strong) mathematical induction, \(P(n)\) is true for all \(n \ge 1\text{.}\)

Prove, using strong induction, that every natural number is either a Fibonacci number or can be written as the sum of distinct Fibonacci numbers.

As with the previous question, we will want to subtract something from \(n\) in the inductive step. There we subtracted the largest power of 2 less than \(n\text{.}\) So what should you subtract here?

Note, you will still need to take care here that the sum you get from the inductive hypothesis, together with the number you subtracted will be a sum of distinct Fibonacci numbers. In fact, you could prove that the Fibonacci numbers in the sum are non-consecutive!

Use induction to prove that if \(n\) people all shake hands with each other, that the total number of handshakes is \(\frac{n(n-1)}{2}\text{.}\)

We have already proved this without using induction, but looking at it inductively sheds light onto the problem (and is fun).

The question you need to answer to complete the inductive step is, how many new handshakes take place when a person \(k+1\) enters the room. Why does adding this give you the correct formula?

Suppose that a particular real number \(x\) has the property that \(x + \frac{1}{x}\) is an integer. Prove that \(x^n + \frac{1}{x^n}\) is an integer for all natural numbers \(n\text{.}\)

You will need to use strong induction. For the inductive case, try multiplying \(\left (x^k + \frac{1}{x^{k}}\right)\left(x+\frac{1}{x}\right)\) and collect which terms together are integers.

Use induction to prove that \(\d\sum_{k=0}^n {n \choose k} = 2^n\text{.}\) That is, the sum of the \(n\) th row of Pascal's Triangle is \(2^n\text{.}\)

Here's the idea: since every entry in Pascal's Triangle is the sum of the two entries above it, we can get the \(k+1\) st row by adding up all the pairs of entry from the \(k\) th row. But doing this uses each entry on the \(k\) th row twice. Thus each time we drop to the next row, we double the total. Of course, row 0 has sum \(1 = 2^0\) (the base case). Now try to make this precise with a formal induction proof. You will use the fact that \({n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}\) for the inductive case.

Use induction to prove \({4 \choose 0} + {5 \choose 1} + {6 \choose 2} + \cdots + {4+n \choose n} = {5+n \choose n}\text{.}\) (This is an example of the hockey stick theorem.)

To see why this works, try it on a copy of Pascal's triangle. We are adding up the entries along a diagonal, starting with the 1 on the left-hand side of the 4th row. Suppose we add up the first 5 entries on this diagonal. The claim is that the sum is the entry below and to the left of the last of these 5 entries. Note that if this is true, and we instead add up the first 6 entries, we will need to add the entry one spot to the right of the previous sum. But these two together give the entry below them, which is below and left of the last of the 6 entries on the diagonal. If you follow that, you can see what is going on. But it is not a great proof. A formal induction proof is needed.

Use the product rule for logarithms ( \(\log(ab) = \log(a) + \log(b)\) ) to prove, by induction on \(n\text{,}\) that \(\log(a^n) = n \log(a)\text{,}\) for all natural numbers \(n \ge 2\text{.}\)

The idea here is that if we take the logarithm of \(a^n\text{,}\) we can increase \(n\) by 1 if we multiply by another \(a\) (inside the logarithm). This results in adding 1 more \(\log(a)\) to the total.

Let \(P(n)\) be the statement \(\log(a^n) = n \log(a)\text{.}\) The base case, \(P(2)\) is true, because \(\log(a^2) = \log(a\cdot a) = \log(a) + \log(a) = 2\log(a)\text{,}\) by the product rule for logarithms. Now assume, for induction, that \(P(k)\) is true. That is, \(\log(a^k) = k\log(a)\text{.}\) Consider \(\log(a^{k+1})\text{.}\) We have

with the last equality due to the inductive hypothesis. But this simplifies to \((k+1) \log(a)\text{,}\) establishing \(P(k+1)\text{.}\) Therefore by the principle of mathematical induction, \(P(n)\) is true for all \(n \ge 2\text{.}\)

Let \(f_1, f_2,\ldots, f_n\) be differentiable functions. Prove, using induction, that

You may assume \((f+g)' = f' + g'\) for any differentiable functions \(f\) and \(g\text{.}\)

You are allowed to assume the base case. For the inductive case, group all but the last function together as one sum of functions, then apply the usual sum of derivatives rule, and then the inductive hypothesis.

Suppose \(f_1, f_2, \ldots, f_n\) are differentiable functions. Use mathematical induction to prove the generalized product rule:

You may assume the product rule for two functions is true.

For the inductive step, we know by the product rule for two functions that

Then use the inductive hypothesis on the first summand, and distribute.

You will prove that the Fibonacci numbers satisfy the identity \(F_n^2 + F_{n+1}^2 = F_{2n+1}\text{.}\) One way to do this is to prove the more general identity,

and realize that when \(m = n\) we get our desired result.

Note that we now have two variables, so we want to prove this for all \(m \ge 0\) and all \(n \ge 0\) at the same time. For each such pair \((m,n)\text{,}\) let \(P(m,n)\) be the statement \(F_mF_n + F_{m+1}F_{n+1} = F_{m+n+1}\)

First fix \(m = 0\) and give a proof by mathematical induction that \(P(0,n)\) holds for all \(n \ge 0\text{.}\) Note this proof will be very easy.

Now fix an arbitrary \(n\) and give a proof by strong mathematical induction that \(P(m,n)\) holds for all \(m \ge 0\text{.}\)

You can now conclude that \(P(m,n)\) holds for all \(m,n\ge 0\text{.}\) Do you believe that? Explain why this sort of induction is valid. For example, why do your proofs above guarantee that \(P(2,3)\) is true?

Given a square, you can cut the square into smaller squares by cutting along lines parallel to the sides of the original square (these lines do not need to travel the entire side length of the original square). For example, by cutting along the lines below, you will divide a square into 6 smaller squares:

Prove, using strong induction, that it is possible to cut a square into \(n\) smaller squares for any \(n \ge 6\text{.}\)

You will need three base cases. This is a very good hint actually, as it suggests that to prove \(P(n)\) is true, you would want to use the fact that \(P(n-3)\) is true. So somehow you need to increase the number of squares by 3.

• Math Article
• Understanding Mathematical Induction With Examples

Mathematical Induction

Mathematical Induction  is introduced to prove certain things and can be explained with this simple example. Garima goes to a garden which has different varieties of flowers. The colour of all the flowers in that garden is yellow. She picks a flower and brings it home. Now if she picks up a rose then what colour is it? Is it too difficult to answer? No, obviously the colour of the rose is yellow as every flower in that garden is yellow. What did we just do here? We used the concept of logical reasoning to deduce the colour of the rose.

Similar to this analysis, in Mathematics the use of the concept of mathematical thinking can be applied to reach conclusions. Consider a mathematical example:

• All the numbers lying on the real number line are known as real numbers
• All the real numbers greater than zero are positive real numbers
• 25 is a real number

From the above statements, we can say that if the first two statements are true then the third one is definitely true. Let us learn more here.

What is Mathematical Induction?

It is the art of proving any statement, theorem or formula which is thought to be true for each and every natural number n .

In mathematics, we come across many statements that are generalize d in the form of n . To check whether that statement is true for all natural numbers we use the concept of  mathematical induction.

This concept of induction is generally based on the fall of dominoes concept.

It’s just like all the dominoes will fall one by one if the first one arranged in the queue is pushed. Similar to this in induction we prove that if a statement is true for the first number (n = 1) and then show that it is true for n = k th  number then it can be generalized that the given statement is true for every n.

It is important to mention here that a set of N natural numbers is the smallest subset of the set of real numbers R with the given property:

Now as N is a subset of the inductive set R then it can be concluded that any subset of R that is inductive must consist of N.

Suppose to find out the sum of positive natural numbers we use the formula:

But is the formula valid? To check the validity of such formula, we use mathematical induction. We check the validity for the smallest possible and then continue for higher values and then if it is true for higher we accept the validity for entire n.

Mathematical Induction Steps

Below are the steps that help in proving the mathematical statements easily.

Step (i): Let us assume an initial value of n for which the statement is true. Here, we need to prove that the statement is true for the initial value of n.

Step (ii): Now, assume that the statement is true for any value of n say n = k. Then, prove the given statement is true for n = k + 1 also. 

Step (iii): Finally, we have to split n = k + 1 into two parts; one part is n = k (already proved in the second step), and we have to prove the other part.

In the above procedure, proving the given statement for the initial value is considered as the base step of mathematical induction and the remaining procedure is known as the inductive step.

Mathematical Induction Examples

Q.1: Show that, 1 + 2 + 3 … … … n = [n(n+1)/2] is true for n = 5.

Solution: Given, n = 5

First, let us find the L.H.S = 1 +2+3+4+5 = 15

Now, R.H.S = [5(5+1)]/2 =  (5 x 6)/2 = 30/2 = 15

Since, L.H.S = R.H.S.

Hence, 1 + 2 + 3 … … … n = [n(n+1)/2] is true for n = 5.

Q.2: Show that 1 + 3 +…+(2n-1) = n 2  for n = 3.

Solution: Given, n =3

2n – 1 = (2 x 3) – 1 = 6 -1 = 5

So, LHS = 1 + 3 + 5 = 9

RHS = 3 2  = 9

Since, L.H.S = R.H.S.

Hence, 1 + 3 +….+(2n-1) = n 2  for n = 3.

Mathematical Induction Problems

Practice the mathematical induction questions given below for the better understanding of the concept.

• Using mathematical induction to prove that 1⋅2⋅3 + 2⋅3⋅4 + … + n(n + 1)(n + 2) = [n(n + 1)(n + 2)(n + 3)]/4  for n ∈ N.
• Prove that 2 n > n for all positive integers n.

3. For every positive integer n, prove that 7 n  – 3 n  is divisible by 4.

Subscribe to our website to learn more and download BYJU’S App to get personalised learning videos.

Put your understanding of this concept to test by answering a few MCQs. Click ‘Start Quiz’ to begin!

Select the correct answer and click on the “Finish” button Check your score and answers at the end of the quiz

Visit BYJU’S for all Maths related queries and study materials

Your result is as below

Request OTP on Voice Call

Leave a Comment Cancel reply

Your Mobile number and Email id will not be published. Required fields are marked *

Post My Comment

Register with BYJU'S & Download Free PDFs

Register with byju's & watch live videos.

Algorithmically Speaking

Mathematical Induction Applied to Graph Theory

Algorithmically speaking - #11: a not-so-common introduction to one of the most powerful mathematical tools..

Hello there, and welcome to a new edition of Algorithmically Speaking!

Today, we will discuss Mathematical Induction, specifically how it can be used in graph theory to demonstrate theorems and propositions.

In this post, I will present one of the fundamental propositions of graph theory and walk you through proving that the proposition holds. I will ensure that the content is accessible to all, regardless of your familiarity with the art of proving theorems in mathematics.

Whether you are a math connoisseur or a total newb to the field, I think you will benefit tremendously from today’s discussion. This example shows why people like me invest a considerable part of their lives diving deeper and deeper into science, specifically looking at the intersection of math and computer science and how these principles can be applied in real-world scenarios.

In order, this is our agenda for today:

🤔 What is mathematical induction? — an introduction to mathematical induction and a classic example of how to use it.

⭐ A fundamental proposition of graph theory — some basic graph theory concepts and a fundamental proposition.

💡 Mathematical Induction to the Rescue — the application of mathematical induction for proving a proposition in graph theory.

This article is part of a chapter on Fundamental Definitions of graph theory in my upcoming book, The Competitive Programmer Graphs Handbook. You can read all the details here: The Competitive Programmer Graphs Handbook Alberto Gonzalez Rosales · Aug 15 Read full story You can support the book by preordering your digital, DRM-free copy, with early and frequent updates, including all future editions. Get early access - $10

Let’s get started!

Algorithmically Speaking is a reader-supported publication. Your support is crucial for the continuation of this work. To receive new posts and support my work, consider becoming a free or paid subscriber.

🤔 What is Mathematical Induction?

Mathematical induction is a method for proving that a statement P(n) is true for every natural number n , that is, that the infinitely many cases P(0), P(1), P(2), P(3),… all hold. This is done by proving a simple case and then showing that if we assume the claim is valid for a given case, the following case is also valid.

A proof by induction consists of two cases. The first, the base case , proves the statement for n=0 without assuming knowledge of other cases. The second case, the induction step , proves that if the statement holds for any given case n=k , it must also hold for the next case n=k+1 . These two steps establish that the statement holds for every natural number n . The base case does not necessarily begin with n=0 , but often with n=1 , and possibly with any fixed natural number n=N , establishing the statement’s truth for all natural numbers n≥N .

Since the premise of mathematical induction is that it works for proving statements concerning natural numbers, it is expected to see it being used in the field of number theory. For example, a classic example is to confirm that the sum of the first n natural numbers is equal to n * (n + 1) / 2 .

More formally,

The proof using mathematical induction would be something like this, formatted as best as I can using the substack editor:

If k = 0, 0 = 0 * (0 + 1) / 2 .

If k > 0, we assume that for a particular k, P(k) holds.

That is, 0 + 1 + … + k = k * (k + 1) / 2 .

It follows that 0 + 1 + … + k + (k + 1) = k * (k + 1) / 2 + (k + 1) .

After some algebraic simplification, we get that 0 + 1 + … + k + (k + 1) = (k + 1) * (k + 2) / 2 . ∎

The induction step is established since P(k + 1) holds . Since the base case and the induction step have been proved true by mathematical induction , the statement P ( n ) holds for every natural number n .

⭐ A Fundamental Proposition of Graph Theory

In the second chapter of my upcoming book , I walk you through a series of basic definitions and concepts in graph theory that lay the basis for fully understanding the forthcoming chapters. One of these basic concepts is what we refer to as degrees .

The degree of a vertex in an undirected graph G is the number of edges incident to that vertex. For a vertex u, the degree of u equals the number of edges e = (x, y) such that x = u or y = u. In directed graphs, the degree concept differs slightly because the edges have direction. The in-degree of a vertex u refers to the number of edges that enter u. The number of edges that leave the vertex is called the out-degree.

For today’s discussion, we will focus on a fundamental proposition that holds for undirected graphs . The proposition is the following,

Let G = < V, E > be an undirected graph. The number of vertices with odd degrees is even.

Let’s see how to prove this statement using mathematical induction!

💡 Mathematical Induction to the Rescue

Here’s the sketch of a proof for the previous proposition, as rigorous as I can make it look in a Substack blog.

Proof. Let k be the number of edges in G:

If k = 0, every vertex has an even degree, so there are zero vertices with an odd degree, which is an even number.

k ⇒ k + 1. Let G =< V, E > be any graph with k + 1 edges. Taking an arbitrary edge e from G, we obtain G′ = G < V, E − e >. By the induction hypothesis, in G′, the number of vertices with odd degrees is even. Three cases can occur when the edge e is added back:

It is added between two vertices with an even degree in G′. In this case, both will have odd degrees, increasing the number of vertices with odd degrees by two, thus keeping this number even.

The edge is added between two vertices with an odd degree in G′. Here, the opposite happens; these nodes will have an even degree, and the number of vertices with an odd degree will decrease by two. This keeps the number of vertices with odd degrees even.

The edge is added between a vertex with an even degree and another with an odd degree in G′. In this case, the parity of the degree of each change. The number of vertices with odd degrees remains the same. ∎

This proof is beautiful. It takes advantage of the fact that mathematical induction works for natural numbers, applying the proof by induction to the number of edges of the graph, which is always a natural number.

We have explored the concept of mathematical induction and its application in proving theorems in graph theory. We have demonstrated how mathematical induction can prove the fundamental proposition that the number of vertices with odd degrees in an undirected graph is even.

By providing step-by-step explanations and examples, we aimed to make the content accessible to those familiar with and new to mathematics. We hope this discussion has provided valuable insights into the intersection of math and computer science and how these principles can be applied.

Stay tuned for more insightful discussions in future editions.

And that’s it for today! If you are finding this newsletter valuable, consider doing any of these:

1) ✉️ Subscribe to the newsletter  — if you aren’t already, consider becoming a free or paid subscriber.

2) 💛 Get early access to my book— thanks to all of you who have contributed to support my writing. The book I'm writing covers this and similar topics in more depth.

Get early access to the book

3)  🍻  Read with your friends  — this newsletter grows because readers share. I don’t use social media too much to advertise my writing. I’m counting on you!

Have a great day! ☀️

Ready for more?

Mathematical Induction and Recursion

• First Online: 29 October 2021

Cite this chapter

• Gerard O’Regan 4  

Part of the book series: Texts in Computer Science ((TCS))

2187 Accesses

Mathematical induction is an important proof technique used in mathematics, and it is often used to establish the truth of a statement for all the natural numbers. There are two parts to a proof by induction, and these are the base step and the inductive step. The first step is termed the base case , and it involves showing that the statement is true for some natural number (usually the number 1). The second step is termed the inductive step , and it involves showing that if the statement is true for some natural number n = k , then the statement is true for its successor n = k + 1. This is often written as P ( k ) → P ( k + 1). Recursion is often used in mathematics to define functions, sequences and sets. However, care is required with a recursive definition to ensure that it actually defines something, and that what is defined makes sense. Recursion defines a concept in terms of itself, and we need to ensure that the definition is not circular (i.e. that it does not lead to a vicious circle).

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save.

• Get 10 units per month
• Download Article/Chapter or eBook
• 1 Unit = 1 Article or 1 Chapter
• Cancel anytime
• Available as PDF
• Read on any device
• Instant download
• Own it forever
• Available as EPUB and PDF
• Compact, lightweight edition
• Dispatched in 3 to 5 business days
• Free shipping worldwide - see info
• Durable hardcover edition

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Four Apt Elementary Examples of Recursion

This definition of mathematical induction covers the base case of n  = 1, and would need to be adjusted if the number specified in the base case is higher.

As before, this definition covers the base case of n  = 1 and would need to be adjusted if the number specified in the base case is higher.

We are taking the Fibonacci sequence as starting at 1, whereas others take it as starting at 0.

We will give an alternate definition of a tree in terms of a connected acyclic graph in Chap. 9 on graph theory.

Meyer B (1990) Introduction to the theory of programming languages. Prentice Hall

Google Scholar  

Download references

Author information

Authors and affiliations.

University of Central Asia, Naryn, Kyrgyzstan

Gerard O’Regan

You can also search for this author in PubMed   Google Scholar

Rights and permissions

Reprints and permissions

Copyright information

© 2021 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this chapter

O’Regan, G. (2021). Mathematical Induction and Recursion. In: Guide to Discrete Mathematics. Texts in Computer Science. Springer, Cham. https://doi.org/10.1007/978-3-030-81588-2_4

Download citation

DOI : https://doi.org/10.1007/978-3-030-81588-2_4

Published : 29 October 2021

Publisher Name : Springer, Cham

Print ISBN : 978-3-030-81587-5

Online ISBN : 978-3-030-81588-2

eBook Packages : Computer Science Computer Science (R0)

Share this chapter

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Publish with us

Policies and ethics

• Find a journal
• Track your research