A graded collection of 20 worked exercises on mathematical induction, designed to build a rigorous understanding of how induction proofs work. Each exercise clearly illustrates:
- how to verify the base case correctly;
- how to state the inductive hypothesis;
- how to apply the hypothesis without logical errors;
- how to carry out the inductive step from \(n\) to \(n+1\).
The goal is not merely to verify formulas, but to understand the logical structure of a proof by induction and to develop the ability to construct rigorous arguments step by step.
Exercise 1 — level ★☆☆☆☆
Prove by induction that:
\[ 1+2+3+\dots+n=\frac{n(n+1)}{2} \]
Proof
Base case
We first verify the statement for \(n=1\).
The left-hand side equals:
\[ 1 \]
The right-hand side equals:
\[ \frac{1(1+1)}{2}=\frac{2}{2}=1 \]
Both sides agree. The statement therefore holds for \(n=1\).
Inductive hypothesis
Assume that the formula holds for some natural number \(n\). This assumption is called the inductive hypothesis.
We thus assume:
\[ 1+2+3+\dots+n=\frac{n(n+1)}{2} \]
It is essential to understand that we are not assuming the formula true for all natural numbers, but only for a fixed, arbitrary value \(n\).
Inductive step
We must show that if the formula holds for \(n\), then it also holds for \(n+1\).
In other words, we need to prove:
\[ 1+2+3+\dots+n+(n+1)=\frac{(n+1)(n+2)}{2} \]
We start from the left-hand side:
\[ 1+2+3+\dots+n+(n+1) \]
At this point we apply the inductive hypothesis, which allows us to replace the sum of the first \(n\) integers with the known expression:
\[ \frac{n(n+1)}{2} \]
We therefore obtain:
\[ 1+2+\dots+n+(n+1) = \frac{n(n+1)}{2}+(n+1) \]
Our goal is now to rewrite this expression in the expected form:
\[ \frac{(n+1)(n+2)}{2} \]
To do so, we factor out \(n+1\):
\[ \frac{n(n+1)}{2}+(n+1) = (n+1)\left(\frac{n}{2}+1\right) \]
Writing \(1\) as \(\frac{2}{2}\) allows us to combine the fractions:
\[ \frac{n}{2}+1 = \frac{n}{2}+\frac{2}{2} = \frac{n+2}{2} \]
Substituting back, we get:
\[ (n+1)\left(\frac{n+2}{2}\right) = \frac{(n+1)(n+2)}{2} \]
We have thus proved that:
\[ 1+2+\dots+n+(n+1) = \frac{(n+1)(n+2)}{2} \]
Conclusion
The statement holds for \(n=1\), and we have shown that its truth for \(n\) implies its truth for \(n+1\).
By the principle of mathematical induction, we conclude that:
\[ 1+2+3+\dots+n=\frac{n(n+1)}{2} \]
for every natural number \(n\geq1\).
Exercise 2 — level ★☆☆☆☆
Prove by induction that:
\[ 1+3+5+\dots+(2n-1)=n^2 \]
Proof
Interpreting the formula
The left-hand side represents the sum of the first \(n\) odd numbers:
\[ 1,3,5,7,\dots \]
The formula states that this sum always equals \(n\) squared.
Base case
We verify the formula for \(n=1\).
The left-hand side equals:
\[ 1 \]
The right-hand side equals:
\[ 1^2=1 \]
Both sides agree. The statement therefore holds for \(n=1\).
Inductive hypothesis
Assume that the formula holds for some natural number \(n\).
We thus assume:
\[ 1+3+5+\dots+(2n-1)=n^2 \]
Inductive step
We must show that the following also holds:
\[ 1+3+5+\dots+(2n-1)+(2n+1)=(n+1)^2 \]
It is worth noting why the term \(2n+1\) appears here.
Indeed:
\[ 2(n+1)-1=2n+2-1=2n+1 \]
So \(2n+1\) is precisely the next odd number in the sequence.
Starting from the left-hand side:
\[ 1+3+5+\dots+(2n-1)+(2n+1) \]
We apply the inductive hypothesis to replace the initial part of the sum:
\[ n^2+(2n+1) \]
This gives:
\[ n^2+2n+1 \]
We recognise this as a perfect square:
\[ n^2+2n+1=(n+1)^2 \]
We have thus proved that:
\[ 1+3+5+\dots+(2n-1)+(2n+1)=(n+1)^2 \]
Conclusion
The statement holds for \(n=1\) and the inductive step has been established.
By the principle of mathematical induction:
\[ 1+3+5+\dots+(2n-1)=n^2 \]
for every \(n\geq1\).
Exercise 3 — level ★★☆☆☆
Prove by induction that:
\[ 1+2+4+8+\dots+2^n=2^{n+1}-1 \]
Proof
Interpreting the formula
The left-hand side represents the sum of the first powers of \(2\):
\[ 2^0+2^1+2^2+\dots+2^n \]
The formula states that this sum can be written in closed form as:
\[ 2^{n+1}-1 \]
Base case
We verify the statement for \(n=0\).
The left-hand side equals:
\[ 2^0=1 \]
The right-hand side equals:
\[ 2^{0+1}-1=2^1-1=2-1=1 \]
Both sides agree. The statement therefore holds for \(n=0\).
Inductive hypothesis
Assume that the formula holds for some natural number \(n\).
We thus assume:
\[ 1+2+4+\dots+2^n=2^{n+1}-1 \]
Inductive step
We must show that the following also holds:
\[ 1+2+4+\dots+2^n+2^{n+1}=2^{n+2}-1 \]
We start from the left-hand side:
\[ 1+2+4+\dots+2^n+2^{n+1} \]
We apply the inductive hypothesis to replace the initial sum:
\[ (2^{n+1}-1)+2^{n+1} \]
Collecting like terms:
\[ 2^{n+1}+2^{n+1}-1 \]
Since:
\[ 2^{n+1}+2^{n+1}=2\cdot2^{n+1} \]
we obtain:
\[ 2\cdot2^{n+1}-1 \]
Applying the laws of exponents:
\[ 2\cdot2^{n+1}=2^{n+2} \]
it follows that:
\[ 2^{n+2}-1 \]
We have thus proved that:
\[ 1+2+4+\dots+2^n+2^{n+1}=2^{n+2}-1 \]
Conclusion
The statement holds for \(n=0\) and the inductive step has been established.
By the principle of mathematical induction:
\[ 1+2+4+8+\dots+2^n=2^{n+1}-1 \]
for every \(n\geq0\).
Exercise 4 — level ★★☆☆☆
Prove by induction that:
\[ 1^2+2^2+3^2+\dots+n^2=\frac{n(n+1)(2n+1)}{6} \]
Proof
Meaning of the formula
The formula provides a closed-form expression for the sum of the squares of the first \(n\) natural numbers.
Rather than adding each term separately:
\[ 1^2+2^2+3^2+\dots+n^2 \]
we can compute directly:
\[ \frac{n(n+1)(2n+1)}{6} \]
Base case
We verify the statement for \(n=1\).
The left-hand side equals:
\[ 1^2=1 \]
The right-hand side equals:
\[ \frac{1(1+1)(2\cdot1+1)}{6} \]
Simplifying:
\[ \frac{1\cdot2\cdot3}{6}=\frac{6}{6}=1 \]
The statement therefore holds for \(n=1\).
Inductive hypothesis
Assume that the formula holds for some natural number \(n\).
We thus assume:
\[ 1^2+2^2+3^2+\dots+n^2 = \frac{n(n+1)(2n+1)}{6} \]
Inductive step
We must show that the following also holds:
\[ 1^2+2^2+\dots+n^2+(n+1)^2 = \frac{(n+1)(n+2)(2n+3)}{6} \]
We start from the left-hand side:
\[ 1^2+2^2+\dots+n^2+(n+1)^2 \]
We now apply the inductive hypothesis:
\[ \frac{n(n+1)(2n+1)}{6}+(n+1)^2 \]
To add the two terms, we rewrite everything with denominator \(6\):
\[ \frac{n(n+1)(2n+1)}{6}+\frac{6(n+1)^2}{6} \]
This gives:
\[ \frac{n(n+1)(2n+1)+6(n+1)^2}{6} \]
We notice that both terms in the numerator share the factor \(n+1\). Factoring it out:
\[ \frac{(n+1)\left[n(2n+1)+6(n+1)\right]}{6} \]
We now expand the expression inside the brackets:
\[ n(2n+1)+6(n+1) \]
Expanding:
\[ 2n^2+n+6n+6 \]
Collecting like terms:
\[ 2n^2+7n+6 \]
We now need to factor this trinomial.
We look for two numbers whose product is:
\[ 2\cdot6=12 \]
and whose sum is:
\[ 7 \]
Those numbers are \(3\) and \(4\). We therefore obtain:
\[ 2n^2+7n+6=(n+2)(2n+3) \]
Substituting back:
\[ \frac{(n+1)(n+2)(2n+3)}{6} \]
which is exactly the formula to be proved.
Conclusion
The statement holds for \(n=1\) and the inductive step has been established.
By the principle of mathematical induction:
\[ 1^2+2^2+3^2+\dots+n^2=\frac{n(n+1)(2n+1)}{6} \]
for every \(n\geq1\).
Exercise 5 — level ★★☆☆☆
Prove by induction that:
\[ 1^3+2^3+3^3+\dots+n^3=\left(\frac{n(n+1)}{2}\right)^2 \]
Proof
Meaning of the formula
The formula states that the sum of the cubes of the first \(n\) natural numbers equals the square of the sum of the first \(n\) natural numbers.
Indeed:
\[ 1+2+3+\dots+n=\frac{n(n+1)}{2} \]
and therefore the right-hand side:
\[ \left(\frac{n(n+1)}{2}\right)^2 \]
is precisely the square of this quantity.
Base case
We verify the statement for \(n=1\).
The left-hand side equals:
\[ 1^3=1 \]
The right-hand side equals:
\[ \left(\frac{1(1+1)}{2}\right)^2 = \left(\frac{2}{2}\right)^2 = 1^2 = 1 \]
Both sides agree. The statement holds for \(n=1\).
Inductive hypothesis
Assume that the formula holds for some natural number \(n\).
We thus assume:
\[ 1^3+2^3+3^3+\dots+n^3 = \left(\frac{n(n+1)}{2}\right)^2 \]
This is the only piece of information available to us in the inductive step: we cannot assume the formula directly for \(n+1\), since that is precisely what we need to prove.
Inductive step
We must show that:
\[ 1^3+2^3+3^3+\dots+n^3+(n+1)^3 = \left(\frac{(n+1)(n+2)}{2}\right)^2 \]
We start from the left-hand side:
\[ 1^3+2^3+3^3+\dots+n^3+(n+1)^3 \]
We apply the inductive hypothesis to the sum of the first \(n\) cubes:
\[ \left(\frac{n(n+1)}{2}\right)^2+(n+1)^3 \]
We expand the first term in order to identify the common factors more clearly:
\[ \left(\frac{n(n+1)}{2}\right)^2 = \frac{n^2(n+1)^2}{4} \]
We therefore obtain:
\[ \frac{n^2(n+1)^2}{4}+(n+1)^3 \]
Both terms contain the factor \((n+1)^2\). Factoring it out:
\[ (n+1)^2\left(\frac{n^2}{4}+n+1\right) \]
We now need to rewrite the expression in parentheses as a perfect square. Bringing everything to the common denominator \(4\):
\[ \frac{n^2}{4}+n+1 = \frac{n^2}{4}+\frac{4n}{4}+\frac{4}{4} \]
hence:
\[ \frac{n^2}{4}+n+1 = \frac{n^2+4n+4}{4} \]
The numerator is a perfect square:
\[ n^2+4n+4=(n+2)^2 \]
Therefore:
\[ \frac{n^2}{4}+n+1 = \frac{(n+2)^2}{4} \]
Substituting back into our expression:
\[ (n+1)^2\cdot\frac{(n+2)^2}{4} \]
Writing the product as a square:
\[ \frac{(n+1)^2(n+2)^2}{4} = \left(\frac{(n+1)(n+2)}{2}\right)^2 \]
We have obtained exactly the required formula for \(n+1\).
Conclusion
The statement holds for \(n=1\) and we have shown that its truth for \(n\) implies its truth for \(n+1\).
By the principle of mathematical induction:
\[ 1^3+2^3+3^3+\dots+n^3=\left(\frac{n(n+1)}{2}\right)^2 \]
for every \(n\geq1\).
Exercise 6 — level ★★☆☆☆
Prove by induction that \(5^n-1\) is divisible by \(4\), for every \(n\geq1\).
Proof
Meaning of the statement
Saying that \(5^n-1\) is divisible by \(4\) means that there exists an integer \(k\) such that:
\[ 5^n-1=4k \]
In an induction proof involving divisibility, the inductive hypothesis is almost always cast in precisely this form.
Base case
We verify the statement for \(n=1\).
We compute:
\[ 5^1-1=5-1=4 \]
Since \(4\) is divisible by \(4\), the statement holds for \(n=1\).
Inductive hypothesis
Assume that the statement holds for some \(n\geq1\).
This means that \(5^n-1\) is divisible by \(4\), so there exists an integer \(k\) such that:
\[ 5^n-1=4k \]
This form is crucial: it allows us to make concrete use of the inductive hypothesis in the calculations that follow.
Inductive step
We must show that \(5^{n+1}-1\) is also divisible by \(4\).
We start from the expression:
\[ 5^{n+1}-1 \]
Writing \(5^{n+1}\) as \(5\cdot5^n\):
\[ 5^{n+1}-1=5\cdot5^n-1 \]
We now want \(5^n-1\) to appear explicitly, since that is the expression featured in the inductive hypothesis.
To this end, we rewrite:
\[ 5\cdot5^n-1=5(5^n-1)+4 \]
We verify this step mentally:
\[ 5(5^n-1)+4=5\cdot5^n-5+4=5\cdot5^n-1 \]
We can now apply the inductive hypothesis:
\[ 5^n-1=4k \]
so:
\[ 5(5^n-1)+4=5\cdot4k+4 \]
Factoring out \(4\):
\[ 5\cdot4k+4=4(5k+1) \]
Since \(5k+1\) is an integer, the expression \(4(5k+1)\) is divisible by \(4\).
Therefore \(5^{n+1}-1\) is divisible by \(4\).
Conclusion
The statement holds for \(n=1\) and we have shown that if \(5^n-1\) is divisible by \(4\), then so is \(5^{n+1}-1\).
By the principle of mathematical induction, \(5^n-1\) is divisible by \(4\) for every \(n\geq1\).
Exercise 7 — level ★★☆☆☆
Prove by induction that \(7^n-1\) is divisible by \(6\), for every \(n\geq1\).
Proof
Meaning of the statement
Saying that \(7^n-1\) is divisible by \(6\) means that \(7^n-1\) is a multiple of \(6\).
In symbols, we need to show that there exists an integer \(k\) such that:
\[ 7^n-1=6k \]
Base case
We verify the statement for \(n=1\).
We compute:
\[ 7^1-1=7-1=6 \]
Since \(6\) is divisible by \(6\), the statement holds for \(n=1\).
Inductive hypothesis
Assume that the statement holds for some \(n\geq1\).
This means that \(7^n-1\) is divisible by \(6\), so there exists an integer \(k\) such that:
\[ 7^n-1=6k \]
The goal of the inductive step will be to make the expression \(7^n-1\) appear explicitly, so that we can substitute using the inductive hypothesis.
Inductive step
We must show that \(7^{n+1}-1\) is divisible by \(6\).
We start from:
\[ 7^{n+1}-1 \]
Writing \(7^{n+1}\) as \(7\cdot7^n\):
\[ 7^{n+1}-1=7\cdot7^n-1 \]
We now rewrite this expression so that \(7^n-1\) appears:
\[ 7\cdot7^n-1=7(7^n-1)+6 \]
Indeed:
\[ 7(7^n-1)+6=7\cdot7^n-7+6=7\cdot7^n-1 \]
Applying the inductive hypothesis \(7^n-1=6k\), we obtain:
\[ 7(7^n-1)+6=7\cdot6k+6 \]
Factoring out \(6\):
\[ 7\cdot6k+6=6(7k+1) \]
Since \(7k+1\) is an integer, \(6(7k+1)\) is divisible by \(6\).
Therefore \(7^{n+1}-1\) is divisible by \(6\).
Conclusion
The statement holds for \(n=1\) and we have shown that divisibility by \(6\) is preserved from step \(n\) to step \(n+1\).
By the principle of mathematical induction, \(7^n-1\) is divisible by \(6\) for every \(n\geq1\).
Exercise 8 — level ★★★☆☆
Prove by induction that:
\[ 11^n-4^n \]
is divisible by \(7\), for every \(n\geq1\).
Proof
Meaning of the statement
We need to show that the difference \(11^n-4^n\) is always a multiple of \(7\).
In other words, we want to prove that there exists an integer \(k\) such that:
\[ 11^n-4^n=7k \]
This exercise is slightly more delicate than the previous ones, because it involves two distinct bases. In the inductive step we will therefore need to manipulate the expression carefully so as to make \(11^n-4^n\) appear.
Base case
We verify the statement for \(n=1\).
We compute:
\[ 11^1-4^1=11-4=7 \]
Since \(7\) is divisible by \(7\), the statement holds for \(n=1\).
Inductive hypothesis
Assume that the statement holds for some \(n\geq1\).
We thus assume that \(11^n-4^n\) is divisible by \(7\), i.e. there exists an integer \(k\) such that:
\[ 11^n-4^n=7k \]
We will use this information in the next step.
Inductive step
We must show that:
\[ 11^{n+1}-4^{n+1} \]
is divisible by \(7\).
Writing the powers at the next step:
\[ 11^{n+1}-4^{n+1}=11\cdot11^n-4\cdot4^n \]
We want \(11^n-4^n\) to appear. To achieve this, we add and subtract the same term \(11\cdot4^n\):
\[ 11\cdot11^n-4\cdot4^n = 11\cdot11^n-11\cdot4^n+11\cdot4^n-4\cdot4^n \]
This step does not change the value of the expression, since we have added and subtracted the same quantity.
We now factor \(11\) from the first two terms and \(4^n\) from the last two:
\[ 11(11^n-4^n)+(11-4)4^n \]
Since \(11-4=7\), we obtain:
\[ 11(11^n-4^n)+7\cdot4^n \]
We can now apply the inductive hypothesis:
\[ 11^n-4^n=7k \]
Substituting:
\[ 11(11^n-4^n)+7\cdot4^n = 11\cdot7k+7\cdot4^n \]
Factoring out \(7\):
\[ 11\cdot7k+7\cdot4^n = 7(11k+4^n) \]
Since \(11k+4^n\) is an integer, the expression is divisible by \(7\).
Therefore:
\[ 7\mid(11^{n+1}-4^{n+1}) \]
Conclusion
The statement holds for \(n=1\) and the inductive step has been established.
By the principle of mathematical induction, \(11^n-4^n\) is divisible by \(7\) for every \(n\geq1\).
Exercise 9 — level ★★★☆☆
Prove by induction that:
\[ 2^n \geq n+1 \]
for every \(n\geq0\).
Proof
Meaning of the statement
The inequality states that the power \(2^n\) grows at least as fast as the linear expression \(n+1\).
In an induction proof involving inequalities, the delicate point is to apply the inductive hypothesis without reversing the direction of the inequality.
Base case
We verify the statement for \(n=0\).
The left-hand side equals:
\[ 2^0=1 \]
The right-hand side equals:
\[ 0+1=1 \]
Therefore:
\[ 2^0\geq0+1 \]
The statement holds for \(n=0\).
Inductive hypothesis
Assume that the statement holds for some \(n\geq0\).
We thus assume:
\[ 2^n\geq n+1 \]
This hypothesis tells us that we may replace \(2^n\) with a quantity no smaller than \(n+1\).
Inductive step
We must show that:
\[ 2^{n+1}\geq n+2 \]
We start from the left-hand side:
\[ 2^{n+1} \]
Writing it as:
\[ 2^{n+1}=2\cdot2^n \]
Since by the inductive hypothesis \(2^n\geq n+1\), multiplying both sides by \(2>0\) preserves the direction of the inequality:
\[ 2\cdot2^n\geq2(n+1) \]
Therefore:
\[ 2^{n+1}\geq2n+2 \]
We now compare \(2n+2\) with \(n+2\), since our goal is to obtain \(n+2\).
Since \(n\geq0\), we have:
\[ 2n+2\geq n+2 \]
Indeed, the difference between the two sides is:
\[ (2n+2)-(n+2)=n\geq0 \]
Combining the two inequalities:
\[ 2^{n+1}\geq2n+2\geq n+2 \]
hence:
\[ 2^{n+1}\geq n+2 \]
Conclusion
The statement holds for \(n=0\) and we have shown that its truth for \(n\) implies its truth for \(n+1\).
By the principle of mathematical induction:
\[ 2^n\geq n+1 \]
for every \(n\geq0\).
Exercise 10 — level ★★★☆☆
Prove by induction that:
\[ 3^n>n \]
for every \(n\geq1\).
Proof
Meaning of the statement
The inequality states that the power \(3^n\) is always greater than the exponent \(n\), for every \(n\geq1\).
Although the statement is intuitively clear — powers of \(3\) grow very rapidly — the goal is to prove it rigorously using induction.
Base case
We verify the statement for \(n=1\).
The left-hand side equals:
\[ 3^1=3 \]
The right-hand side equals:
\[ 1 \]
Since:
\[ 3>1 \]
the statement holds for \(n=1\).
Inductive hypothesis
Assume that the statement holds for some \(n\geq1\).
We thus assume:
\[ 3^n>n \]
This is the information we will use to establish the inequality at the next step.
Inductive step
We must show that:
\[ 3^{n+1}>n+1 \]
We start from:
\[ 3^{n+1} \]
Writing:
\[ 3^{n+1}=3\cdot3^n \]
Using the inductive hypothesis \(3^n>n\) and multiplying by \(3>0\), we obtain:
\[ 3\cdot3^n>3n \]
Therefore:
\[ 3^{n+1}>3n \]
We now compare \(3n\) with \(n+1\).
For \(n\geq1\), we have:
\[ 3n>n+1 \]
Indeed:
\[ 3n-(n+1)=2n-1 \]
and, if \(n\geq1\), then:
\[ 2n-1\geq1>0 \]
Therefore:
\[ 3n>n+1 \]
Combining:
\[ 3^{n+1}>3n>n+1 \]
hence:
\[ 3^{n+1}>n+1 \]
Conclusion
The statement holds for \(n=1\) and the inductive step has been established.
By the principle of mathematical induction:
\[ 3^n>n \]
for every \(n\geq1\).
Exercise 11 — level ★★★★☆
Prove by induction that:
\[ 2^n < n! \]
for every \(n\geq4\).
Proof
Meaning of the statement
The inequality compares a power with a factorial.
The factorial \(n!\) is the product:
\[ n!=1\cdot2\cdot3\cdot\dots\cdot n \]
The statement asserts that, starting from \(n=4\), the factorial is always greater than \(2^n\).
Base case
We verify the statement for \(n=4\).
The left-hand side equals:
\[ 2^4=16 \]
The right-hand side equals:
\[ 4!=1\cdot2\cdot3\cdot4=24 \]
Since:
\[ 16<24 \]
the statement holds for \(n=4\).
Inductive hypothesis
Assume that the statement holds for some \(n\geq4\).
We thus assume:
\[ 2^n < n! \]
This hypothesis allows us to compare \(2^n\) with \(n!\). In the next step we will need to compare \(2^{n+1}\) with \((n+1)!\).
Inductive step
We must show that:
\[ 2^{n+1}<(n+1)! \]
We start from the left-hand side:
\[ 2^{n+1} \]
Writing it as:
\[ 2^{n+1}=2\cdot2^n \]
By the inductive hypothesis we know that:
\[ 2^n < n! \]
Multiplying both sides by \(2>0\), we obtain:
\[ 2\cdot2^n<2\cdot n! \]
Therefore:
\[ 2^{n+1}<2\cdot n! \]
We now relate \(2\cdot n!\) to \((n+1)!\). Recalling that:
\[ (n+1)!=(n+1)\cdot n! \]
Since \(n\geq4\), we have:
\[ n+1\geq5 \]
therefore:
\[ 2 < n+1 \]
Multiplying by \(n!>0\), we obtain:
\[ 2\cdot n!<(n+1)\cdot n! \]
that is:
\[ 2\cdot n!<(n+1)! \]
Combining the two inequalities:
\[ 2^{n+1}<2\cdot n!<(n+1)! \]
hence:
\[ 2^{n+1}<(n+1)! \]
Conclusion
The statement holds for \(n=4\) and we have shown that its truth for \(n\) implies its truth for \(n+1\).
By the principle of mathematical induction:
\[ 2^n < n! \]
for every \(n\geq4\).
Exercise 12 — level ★★★★☆
Prove by induction that:
\[ 4^n\geq3n+1 \]
for every \(n\geq0\).
Proof
Meaning of the statement
The statement compares exponential growth, represented by \(4^n\), with linear growth, represented by \(3n+1\).
Induction allows us to prove that this inequality holds for every natural number \(n\geq0\), without having to check individual cases one by one.
Base case
We verify the statement for \(n=0\).
The left-hand side equals:
\[ 4^0=1 \]
The right-hand side equals:
\[ 3\cdot0+1=1 \]
Both sides are equal, so:
\[ 4^0\geq3\cdot0+1 \]
The statement holds for \(n=0\).
Inductive hypothesis
Assume that the statement holds for some \(n\geq0\).
We thus assume:
\[ 4^n\geq3n+1 \]
We will use this information to establish the inequality at the next step.
Inductive step
We must show that:
\[ 4^{n+1}\geq3(n+1)+1 \]
Since:
\[ 4^{n+1}=4\cdot4^n \]
we can apply the inductive hypothesis. Since \(4>0\), multiplying by \(4\) preserves the direction of the inequality:
\[ 4\cdot4^n\geq4(3n+1) \]
Therefore:
\[ 4^{n+1}\geq12n+4 \]
We now want to obtain:
\[ 3(n+1)+1 \]
Expanding:
\[ 3(n+1)+1=3n+3+1=3n+4 \]
We therefore compare \(12n+4\) with \(3n+4\).
Since \(n\geq0\), we have:
\[ 12n+4\geq3n+4 \]
Indeed:
\[ (12n+4)-(3n+4)=9n\geq0 \]
Therefore:
\[ 12n+4\geq3n+4=3(n+1)+1 \]
Combining:
\[ 4^{n+1}\geq12n+4\geq3(n+1)+1 \]
hence:
\[ 4^{n+1}\geq3(n+1)+1 \]
Conclusion
The statement holds for \(n=0\) and we have shown that its validity for \(n\) implies its validity for \(n+1\).
By the principle of mathematical induction:
\[ 4^n\geq3n+1 \]
for every \(n\geq0\).
Exercise 13 — level ★★★★☆
Prove by induction that:
\[ 1+3+3^2+\dots+3^n=\frac{3^{n+1}-1}{2} \]
for every \(n\geq0\).
Proof
Meaning of the formula
The left-hand side is the sum of the first powers of \(3\), starting from \(3^0=1\):
\[ 1+3+3^2+\dots+3^n \]
The formula states that this sum can be computed directly as:
\[ \frac{3^{n+1}-1}{2} \]
Base case
We verify the statement for \(n=0\).
The left-hand side equals:
\[ 1 \]
The right-hand side equals:
\[ \frac{3^{0+1}-1}{2} = \frac{3-1}{2} = \frac{2}{2} = 1 \]
Both sides agree. The statement holds for \(n=0\).
Inductive hypothesis
Assume that the formula holds for some \(n\geq0\).
We thus assume:
\[ 1+3+3^2+\dots+3^n=\frac{3^{n+1}-1}{2} \]
Inductive step
We must show that:
\[ 1+3+3^2+\dots+3^n+3^{n+1} = \frac{3^{n+2}-1}{2} \]
We start from the left-hand side:
\[ 1+3+3^2+\dots+3^n+3^{n+1} \]
We apply the inductive hypothesis to the initial part of the sum:
\[ \frac{3^{n+1}-1}{2}+3^{n+1} \]
Bringing everything to the common denominator:
\[ \frac{3^{n+1}-1}{2}+\frac{2\cdot3^{n+1}}{2} \]
Adding the numerators:
\[ \frac{3^{n+1}-1+2\cdot3^{n+1}}{2} \]
We now collect the terms involving \(3^{n+1}\):
\[ 3^{n+1}+2\cdot3^{n+1}=3\cdot3^{n+1} \]
Therefore:
\[ \frac{3\cdot3^{n+1}-1}{2} \]
By the laws of exponents:
\[ 3\cdot3^{n+1}=3^{n+2} \]
We thus obtain:
\[ \frac{3^{n+2}-1}{2} \]
which is exactly the formula at step \(n+1\).
Conclusion
The statement holds for \(n=0\) and we have shown that its truth for \(n\) implies its truth for \(n+1\).
By the principle of mathematical induction:
\[ 1+3+3^2+\dots+3^n=\frac{3^{n+1}-1}{2} \]
for every \(n\geq0\).
Exercise 14 — level ★★★★☆
Prove by induction that:
\[ 8^n-1 \]
is divisible by \(7\), for every \(n\geq1\).
Proof
Meaning of the statement
We need to show that \(8^n-1\) is always a multiple of \(7\).
Equivalently, we need to show that there exists an integer \(k\) such that:
\[ 8^n-1=7k \]
Base case
We verify the statement for \(n=1\).
We compute:
\[ 8^1-1=8-1=7 \]
Since \(7\) is divisible by \(7\), the statement holds for \(n=1\).
Inductive hypothesis
Assume that the statement holds for some \(n\geq1\).
Then there exists an integer \(k\) such that:
\[ 8^n-1=7k \]
In the inductive step we will need to make \(8^n-1\) appear explicitly, so that we can substitute using the inductive hypothesis.
Inductive step
We must show that \(8^{n+1}-1\) is divisible by \(7\).
We start from:
\[ 8^{n+1}-1 \]
Writing \(8^{n+1}\) as:
\[ 8^{n+1}=8\cdot8^n \]
we get:
\[ 8^{n+1}-1=8\cdot8^n-1 \]
We now rewrite the expression so that \(8^n-1\) appears:
\[ 8\cdot8^n-1=8(8^n-1)+7 \]
Indeed:
\[ 8(8^n-1)+7=8\cdot8^n-8+7=8\cdot8^n-1 \]
Applying the inductive hypothesis \(8^n-1=7k\), we obtain:
\[ 8(8^n-1)+7=8\cdot7k+7 \]
Factoring out \(7\):
\[ 8\cdot7k+7=7(8k+1) \]
Since \(8k+1\) is an integer, the expression \(7(8k+1)\) is divisible by \(7\).
Therefore \(8^{n+1}-1\) is divisible by \(7\).
Conclusion
The statement holds for \(n=1\) and we have shown that divisibility is preserved from step \(n\) to step \(n+1\).
By the principle of mathematical induction, \(8^n-1\) is divisible by \(7\) for every \(n\geq1\).
Exercise 15 — level ★★★★☆
Prove by induction that:
\[ 9^n-1 \]
is divisible by \(8\), for every \(n\geq1\).
Proof
Meaning of the statement
We need to show that \(9^n-1\) is always a multiple of \(8\).
In symbols, we want to prove that there exists an integer \(k\) such that:
\[ 9^n-1=8k \]
Base case
We verify the statement for \(n=1\).
We compute:
\[ 9^1-1=9-1=8 \]
Since \(8\) is divisible by \(8\), the statement holds for \(n=1\).
Inductive hypothesis
Assume that the statement holds for some \(n\geq1\).
Then there exists an integer \(k\) such that:
\[ 9^n-1=8k \]
Inductive step
We must show that \(9^{n+1}-1\) is divisible by \(8\).
We start from:
\[ 9^{n+1}-1 \]
Writing:
\[ 9^{n+1}=9\cdot9^n \]
we get:
\[ 9^{n+1}-1=9\cdot9^n-1 \]
We want \(9^n-1\) to appear, since that is the expression controlled by the inductive hypothesis.
We rewrite:
\[ 9\cdot9^n-1=9(9^n-1)+8 \]
Indeed:
\[ 9(9^n-1)+8=9\cdot9^n-9+8=9\cdot9^n-1 \]
Applying the inductive hypothesis:
\[ 9^n-1=8k \]
we obtain:
\[ 9(9^n-1)+8=9\cdot8k+8 \]
Factoring out \(8\):
\[ 9\cdot8k+8=8(9k+1) \]
Since \(9k+1\) is an integer, the expression is divisible by \(8\).
Therefore \(9^{n+1}-1\) is divisible by \(8\).
Conclusion
The statement holds for \(n=1\) and the inductive step has been established.
By the principle of mathematical induction, \(9^n-1\) is divisible by \(8\) for every \(n\geq1\).
Exercise 16 — level ★★★★★
Prove by induction that:
\[ 1\cdot1!+2\cdot2!+3\cdot3!+\dots+n\cdot n!=(n+1)!-1 \]
for every \(n\geq1\).
Proof
Meaning of the formula
The left-hand side is a sum whose terms have the form:
\[ k\cdot k! \]
The formula states that this sum simplifies to a remarkably compact expression:
\[ (n+1)!-1 \]
The key observation in this exercise is recognising how the next term \((n+1)(n+1)!\) combines with \((n+1)!\).
Base case
We verify the statement for \(n=1\).
The left-hand side equals:
\[ 1\cdot1!=1 \]
The right-hand side equals:
\[ (1+1)!-1=2!-1=2-1=1 \]
Both sides agree. The statement holds for \(n=1\).
Inductive hypothesis
Assume that the formula holds for some \(n\geq1\).
We thus assume:
\[ 1\cdot1!+2\cdot2!+\dots+n\cdot n!=(n+1)!-1 \]
Inductive step
We must show that:
\[ 1\cdot1!+2\cdot2!+\dots+n\cdot n!+(n+1)(n+1)!=(n+2)!-1 \]
We start from the left-hand side:
\[ 1\cdot1!+2\cdot2!+\dots+n\cdot n!+(n+1)(n+1)! \]
We apply the inductive hypothesis to the sum up to \(n\):
\[ (n+1)!-1+(n+1)(n+1)! \]
We now factor out \((n+1)!\):
\[ (n+1)!+(n+1)(n+1)!-1 \]
Both of the first two terms contain \((n+1)!\), so:
\[ (n+1)!\left[1+(n+1)\right]-1 \]
Simplifying the bracket:
\[ 1+(n+1)=n+2 \]
hence:
\[ (n+1)!(n+2)-1 \]
Since:
\[ (n+2)!=(n+2)(n+1)! \]
we obtain:
\[ (n+2)!-1 \]
which is exactly the required formula at step \(n+1\).
Conclusion
The statement holds for \(n=1\) and we have shown that its truth for \(n\) implies its truth for \(n+1\).
By the principle of mathematical induction:
\[ 1\cdot1!+2\cdot2!+3\cdot3!+\dots+n\cdot n!=(n+1)!-1 \]
for every \(n\geq1\).
Exercise 17 — level ★★★★★
Prove by induction that:
\[ 1+\frac{1}{2}+\frac{1}{4}+\dots+\frac{1}{2^n} = 2-\frac{1}{2^n} \]
for every \(n\geq0\).
Proof
Meaning of the formula
The left-hand side is a sum of negative powers of \(2\), that is, a geometric series:
\[ 1+\frac{1}{2}+\frac{1}{4}+\dots+\frac{1}{2^n} \]
The formula states that this sum equals:
\[ 2-\frac{1}{2^n} \]
The term \(\frac{1}{2^n}\) measures how far the partial sum still is from \(2\).
Base case
We verify the statement for \(n=0\).
The left-hand side contains only the first term:
\[ 1 \]
The right-hand side equals:
\[ 2-\frac{1}{2^0}=2-1=1 \]
Both sides agree. The statement holds for \(n=0\).
Inductive hypothesis
Assume that the formula holds for some \(n\geq0\).
We thus assume:
\[ 1+\frac{1}{2}+\frac{1}{4}+\dots+\frac{1}{2^n} = 2-\frac{1}{2^n} \]
This hypothesis describes the sum up to the term \(\frac{1}{2^n}\). In the next step we will need to add the new term \(\frac{1}{2^{n+1}}\).
Inductive step
We must show that:
\[ 1+\frac{1}{2}+\frac{1}{4}+\dots+\frac{1}{2^n}+\frac{1}{2^{n+1}} = 2-\frac{1}{2^{n+1}} \]
We start from the left-hand side:
\[ 1+\frac{1}{2}+\frac{1}{4}+\dots+\frac{1}{2^n}+\frac{1}{2^{n+1}} \]
We apply the inductive hypothesis to the sum up to \(\frac{1}{2^n}\):
\[ 2-\frac{1}{2^n}+\frac{1}{2^{n+1}} \]
We now simplify the last two terms:
\[ -\frac{1}{2^n}+\frac{1}{2^{n+1}} \]
We observe that:
\[ \frac{1}{2^n}=\frac{2}{2^{n+1}} \]
since \(2^{n+1}=2\cdot2^n\).
Therefore:
\[ -\frac{1}{2^n}+\frac{1}{2^{n+1}} = -\frac{2}{2^{n+1}}+\frac{1}{2^{n+1}} \]
Adding the fractions:
\[ -\frac{2}{2^{n+1}}+\frac{1}{2^{n+1}} = -\frac{1}{2^{n+1}} \]
Therefore:
\[ 2-\frac{1}{2^n}+\frac{1}{2^{n+1}} = 2-\frac{1}{2^{n+1}} \]
We have obtained exactly the required formula for \(n+1\).
Conclusion
The statement holds for \(n=0\) and the inductive step has been established.
By the principle of mathematical induction:
\[ 1+\frac{1}{2}+\frac{1}{4}+\dots+\frac{1}{2^n} = 2-\frac{1}{2^n} \]
for every \(n\geq0\).
Exercise 18 — level ★★★★★
Prove by induction that:
\[ \sum_{k=1}^{n} k(k+1)=\frac{n(n+1)(n+2)}{3} \]
for every \(n\geq1\).
Proof
Meaning of the formula
The notation:
\[ \sum_{k=1}^{n} k(k+1) \]
denotes the sum of terms of the form \(k(k+1)\), as \(k\) ranges from \(1\) to \(n\).
Written out explicitly:
\[ \sum_{k=1}^{n} k(k+1) = 1\cdot2+2\cdot3+3\cdot4+\dots+n(n+1) \]
The formula states that this sum can be written in closed form as:
\[ \frac{n(n+1)(n+2)}{3} \]
Base case
We verify the statement for \(n=1\).
The left-hand side equals:
\[ \sum_{k=1}^{1} k(k+1)=1(1+1)=2 \]
The right-hand side equals:
\[ \frac{1(1+1)(1+2)}{3} = \frac{1\cdot2\cdot3}{3} = 2 \]
Both sides agree. The statement holds for \(n=1\).
Inductive hypothesis
Assume that the formula holds for some \(n\geq1\).
We thus assume:
\[ \sum_{k=1}^{n} k(k+1)=\frac{n(n+1)(n+2)}{3} \]
This hypothesis describes the sum up to the term \(n(n+1)\). In the next step we will need to add the term corresponding to \(k=n+1\).
Inductive step
We must show that:
\[ \sum_{k=1}^{n+1} k(k+1)=\frac{(n+1)(n+2)(n+3)}{3} \]
We write the sum up to \(n+1\) by separating the last term:
\[ \sum_{k=1}^{n+1} k(k+1) = \sum_{k=1}^{n} k(k+1)+(n+1)(n+2) \]
We now apply the inductive hypothesis:
\[ \frac{n(n+1)(n+2)}{3}+(n+1)(n+2) \]
Both terms share the factor \((n+1)(n+2)\). Factoring it out:
\[ (n+1)(n+2)\left(\frac{n}{3}+1\right) \]
We now simplify the expression in parentheses:
\[ \frac{n}{3}+1=\frac{n}{3}+\frac{3}{3}=\frac{n+3}{3} \]
Substituting back:
\[ (n+1)(n+2)\cdot\frac{n+3}{3} \]
that is:
\[ \frac{(n+1)(n+2)(n+3)}{3} \]
We have obtained exactly the required formula for \(n+1\).
Conclusion
The statement holds for \(n=1\) and the inductive step has been established.
By the principle of mathematical induction:
\[ \sum_{k=1}^{n} k(k+1)=\frac{n(n+1)(n+2)}{3} \]
for every \(n\geq1\).
Exercise 19 — level ★★★★★
Prove by induction that:
\[ 2^n>n^2 \]
for every \(n\geq5\).
Proof
Meaning of the statement
The inequality compares exponential growth, \(2^n\), with polynomial growth, \(n^2\).
The statement does not hold for all small values of \(n\). For instance, when \(n=2\) we have \(2^2=4\) and \(2^2=4\), so the strict inequality fails.
For this reason the induction proof starts from \(n=5\).
Base case
We verify the statement for \(n=5\).
The left-hand side equals:
\[ 2^5=32 \]
The right-hand side equals:
\[ 5^2=25 \]
Since:
\[ 32>25 \]
the statement holds for \(n=5\).
Inductive hypothesis
Assume that the statement holds for some \(n\geq5\).
We thus assume:
\[ 2^n>n^2 \]
We will use this information to establish the inequality at the next step.
Inductive step
We must show that:
\[ 2^{n+1}>(n+1)^2 \]
We start from the left-hand side:
\[ 2^{n+1} \]
Writing:
\[ 2^{n+1}=2\cdot2^n \]
By the inductive hypothesis:
\[ 2^n>n^2 \]
Multiplying by \(2>0\), we obtain:
\[ 2\cdot2^n>2n^2 \]
Therefore:
\[ 2^{n+1}>2n^2 \]
We now show that \(2n^2\) is greater than \((n+1)^2\). Indeed, if:
\[ 2n^2>(n+1)^2 \]
then, combining the two inequalities, we will obtain:
\[ 2^{n+1}>2n^2>(n+1)^2 \]
We therefore verify that:
\[ 2n^2>(n+1)^2 \]
Moving everything to the left:
\[ 2n^2-(n+1)^2 \]
Expanding the square:
\[ (n+1)^2=n^2+2n+1 \]
hence:
\[ 2n^2-(n+1)^2 = 2n^2-(n^2+2n+1) \]
that is:
\[ n^2-2n-1 \]
We rewrite this expression in a convenient form:
\[ n^2-2n-1=(n-1)^2-2 \]
Since \(n\geq5\), we have \(n-1\geq4\), so:
\[ (n-1)^2\geq4^2=16 \]
Consequently:
\[ (n-1)^2-2\geq16-2=14>0 \]
Therefore:
\[ 2n^2-(n+1)^2>0 \]
and hence:
\[ 2n^2>(n+1)^2 \]
Combining:
\[ 2^{n+1}>2n^2>(n+1)^2 \]
we obtain:
\[ 2^{n+1}>(n+1)^2 \]
Conclusion
The statement holds for \(n=5\) and we have shown that its truth for \(n\) implies its truth for \(n+1\).
By the principle of mathematical induction:
\[ 2^n>n^2 \]
for every \(n\geq5\).
Exercise 20 — level ★★★★★
Prove by induction that every natural number \(n\geq2\) is either prime or a product of prime numbers.
Proof
Meaning of the statement
This statement expresses the existence part of the fundamental theorem of arithmetic: every natural number greater than or equal to \(2\) can be expressed as a product of prime factors.
In this exercise we will use strong induction. Unlike ordinary induction, in strong induction we may assume, in order to prove the statement for \(n\), that it holds for all natural numbers between \(2\) and \(n-1\).
This form of induction is natural here, because if a number is not prime, it can be written as a product of two smaller numbers.
Base case
We verify the statement for \(n=2\).
The number \(2\) is prime.
Therefore the statement holds for \(n=2\).
Strong induction hypothesis
Assume that the statement holds for all natural numbers \(m\) such that:
\[ 2\leq m\leq n \]
That is, every natural number between \(2\) and \(n\) is either prime or a product of prime numbers.
Inductive step
We must show that the statement holds for \(n+1\).
Consider the number \(n+1\).
There are two cases.
Case 1: \(n+1\) is prime
If \(n+1\) is prime, the statement holds immediately.
Indeed, the statement requires the number to be either prime or a product of primes; in this case it is directly prime.
Case 2: \(n+1\) is not prime
If \(n+1\) is not prime, then by definition there exist two natural numbers \(a\) and \(b\), both greater than \(1\), such that:
\[ n+1=ab \]
Moreover, since \(a>1\) and \(b>1\), both factors are strictly less than \(n+1\).
Therefore:
\[ 2\leq a\leq n \qquad \text{and} \qquad 2\leq b\leq n \]
We can now apply the strong induction hypothesis to both \(a\) and \(b\).
By hypothesis, \(a\) is either prime or a product of prime numbers.
Likewise, \(b\) is either prime or a product of prime numbers.
Since:
\[ n+1=ab \]
and both \(a\) and \(b\) are primes or products of primes, it follows that \(n+1\) is also a product of prime numbers.
Conclusion
We have shown that if the statement holds for all numbers from \(2\) to \(n\), then it also holds for \(n+1\).
Since the statement holds for \(n=2\), by the principle of strong induction we conclude that every natural number \(n\geq2\) is either prime or a product of prime numbers.