Activity 5.3.1.
Prove \(\sum_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}{6}\) for all \(n\geq 1\) by induction. Make sure your proof follows the form above.
Section 5.3 More Mathematical Induction
In the last section we introduced mathematical induction by looking at proofs involving summation formulas. In this section we look at some more examples, including divisibility proofs and inequality proofs.
As in the previous section, we will assume \(n\in \mathbb{Z}\text{.}\) We will continue to use the same Structure of a Mathematical Induction Proof. Before looking at new examples of induction proofs, let’s make sure we can write a summation proof.
Our next example looks at using induction to prove a divisibility statement. We proved several properties of divisibility in Section 4.3. Now we want to be able to use those properties to simplify our induction proofs. Remember, a written proof just needs to make a clear series of logical steps. It does not need to explain how the writer thought to do those steps.
Example 5.3.1. Proof by Induction: Divisibility.
Prove \(3\mid (n^3-n)\) for \(n\geq 0\text{.}\)
Proof.
Base Step: Let \(n=0\text{.}\) Then \(n^3-n=0^3-0=0\text{.}\) We know \(3\mid 0\text{.}\)
Thus, \(3\mid (n^3-n)\) for \(n=0\text{.}\)
Induction Step:
Assume \(3\mid (k^3-k)\) for some \(k\geq 0\text{.}\)
Show \(3\mid ((k+1)^3-(k+1))\text{.}\)
Scratchwork: before proving the induction step, we might need to do some scratchwork. This is not part of the proof, but will help us structure a clear proof. We can do some algebra on the expression we in the “show” statement:
\begin{align*}
(k+1)^3-(k+1)&=k^3+3k^2+3k+1-k-1\\
&=(k^3-k)+3k^2+3k\ \ \textrm{ rearranged terms and cancelled 1's}
\end{align*}
But by our assumption, \(3\mid (k^3-k)\) and since the remaining terms are multiples of 3, \(3\mid 3k^2+3k\text{.}\)
Now we are ready to use our scratch work to write the proof of the induction step.
Proof of induction step:
\begin{align*}
3&\mid (k^3-k)\ \ \textrm{ by the induction assumption}\\
3&\mid (k^3-k)+3k^2+3k\ \ \textrm{ since we just added multiples of 3}\\
3&\mid (k^3-k)+3k^2+3k+1-1\ \ \textrm{ since 1-1 is 0}\\
3&\mid k^3+3k^2+3k+1-k-1\ \ \textrm{ rearranged terms}\\
3&\mid ((k+1)^3-(k+1)).
\end{align*}
Which is what we wanted to show.
Hence, by induction \(3\mid (n^3-n)\) for \(n\geq 0\text{.}\)
Some comments about divisibility proofs:
- You will likely need to do scratchwork. Do not include the scratchwork in your actual proof.
- The point of the proof is that the reader can follow all of the steps. You do not need to explain where your choices came from. For example, in the proof in Example 5.3.1, it might not be obvious why you should add \(3k^2+3k\text{,}\) but the reader just needs to know that 3 divides the expression, which is clear.
- Divisibility proofs in this form can be challenging to do at first, but with practice, they often end up being some of the easier induction proofs to do, as they all follow a similar format.
Let’s try another example.
Example 5.3.2. Proof by Induction: Divisibility, Again.
Prove \(3\mid (2^{2n}-1)\) for \(n\geq 0\text{.}\)
Proof.
Base Step: Let \(n=0\text{.}\) Then \(2^{2n}-1=2^{0}-1=0\text{.}\) We know \(3\mid 0\text{.}\)
Thus, \(3\mid (2^{2n}-1)\) for \(n=0\text{.}\)
Induction Step:
Assume \(3\mid (2^{2k}-1)\) for some \(k\geq 0\text{.}\)
Show \(3\mid (2^{2(k+1)}-1)\text{.}\)
Scratchwork:
\begin{align*}
2^{2(k+1)}-1&=2^{2k+2}-1\\
&=(2^2)(2^{2k})-1\ \ \textrm{ used exponent rules to rewrite}\\
&=(4)(2^{2k})-1\\
&=(3+1)(2^{2k})-1\ \ \textrm{ maybe not an obvious step,}\\
&\ \ \ \ \ \ \ \textrm{ but we are looking for multiples of 3}\\
&=3\cdot 2^{2k}+2^{2k}-1\ \ \textrm{ distribute}
\end{align*}
But by our assumption, \(3\mid 2^{2k}-1\) and since the remaining term is a multiple of 3, \(3\mid 3\cdot 2^{2k}+2^{2k}-1\text{.}\)
Now we are ready to use our scratchwork to write the proof of the induction step.
Proof of induction step:
\begin{align*}
3&\mid 2^{2k}-1\ \ \textrm{ by the induction assumption}\\
3&\mid 2^{2k}-1+3\cdot 2^{2k}\ \ \textrm{ since we just added a multiple of 3}\\
3&\mid (3+1)(2^{2k})-1\ \ \textrm{ factored out } 2^{2k}\\
3&\mid (4)(2^{2k})-1\\
3&\mid (2^2)(2^{2k})-1\\
3&\mid (2^{2k+2})-1\\
3&\mid (2^{2(k+1)})-1
\end{align*}
Which is what we wanted to show.
Hence, by induction \(3\mid (2^{2n}-1)\) for \(n\geq 0\text{.}\)
Activity 5.3.2.
Prove \(8 \mid 3^{2n}-1\) for all \(n\geq 0\) by induction. It may be helpful to do scratchwork first.
Now we apply induction to statements involving inequalities. These will be some of the most challenging induction proofs as they often take a bit more trial and error in the scratchwork. When dealing with equalities, you know that you have to add the same thing to both sides. However, with inequalities you can change one side as long as you maintain the inequality. For example, if you know \(P>Q\text{,}\) then you also know \(P+2>Q\text{.}\) The fact that we can change one side of the expression makes it more challenging to see what steps to take.
Example 5.3.3. Proof by Induction: Inequality.
Prove \(2n+1< 2^n\) for \(n\geq 3\text{.}\)
Proof.
Base Step: Let \(n=3\text{.}\) Then \(2n+1=2(3)+1=7\text{,}\) and \(2^n=2^3=8\) We know \(7<8\text{.}\)
Thus, \(2n+1< 2^n\) for \(n=3\text{.}\)
Induction Step:
Assume \(2k+1< 2^k\) for some \(k\geq 3\text{.}\)
Show \(2(k+1)+1< 2^{k+1}\text{.}\)
Scratchwork:
\begin{gather*}
\text{LHS: } 2(k+1)+1=2k+2+1=2k+1+2\\
\text{RHS: } 2^{k+1}=2(2^k)
\end{gather*}
Now we want to make a useful observation: in the LHS expression we are addding. In the RHS expression we are multiplying. We need a way to go between them. One way is to notice that \(2(A)=A+A\text{.}\) Then
\begin{gather*}
2^{k+1}=2(2^k)=2^k+2^k
\end{gather*}
We know \(2k+1< 2^k\) and \(2<2^k\text{,}\) so we can put all this together into the proof.
Proof of induction step:
\begin{align*}
2k+1< 2^k\ \ \textrm{ by the induction assumption}\\
2(k+1)+1 &= 2k+2+1\\
&=2k+1+2\\
&<2^k+2\ \ \textrm{ by the induction assumption}\\
&<2^k+2^k\ \ \textrm{ since } 2< 2^k\\
&=2(2^k)\\
&=2^{k+1}
\end{align*}
Thus, \(2(k+1)+1< 2^{k+1}\text{,}\) which is what we wanted to show.
Hence, by induction \(2n+1< 2^n\) for \(n\geq 3\text{.}\)
Reading Questions Check Your Understanding
1.
Suppose you want to prove \(8\mid 3^{2n}-1\text{.}\) Show the statement holds for \(n=0\text{.}\)
Hint.
Remember to just start with \(3^{2n}-1\text{.}\) Do not assume 8 divides it.
2.
Suppose you want to prove \(8\mid 3^{2n}-1\text{.}\) Show the statement holds for \(n=1\text{.}\)
Hint.
Remember to just start with \(3^{2n}-1\text{.}\) Do not assume 8 divides it.
3.
Suppose you want to prove \(8\mid 3^{2n}-1\text{.}\) What should you assume in the induction step?
4.
Suppose you want to prove \(8\mid 3^{2n}-1\text{.}\) What should you show in the induction step?
5.
If you know \(8\mid 3^{2k}-1\text{,}\) rewrite \(3^{2(k+1)}-1\) so that it is a sum of terms that are multiples of 8.
Hint.
Be careful with the algebra, especially with rules of exponents. It is also helpful to notice that \(3^2=9=8+1\text{.}\)
Exercises Exercises
1.
Observe that
\begin{align*}
\frac{1}{1\cdot 3}\amp =\frac{1}{3}\\
\frac{1}{1\cdot 3}+\frac{1}{3\cdot 5}\amp =\frac{2}{5}\\
\frac{1}{1\cdot 3}+\frac{1}{3\cdot 5}+\frac{1}{5\cdot 7}\amp =\frac{3}{7}\\
\frac{1}{1\cdot 3}+\frac{1}{3\cdot 5}+\frac{1}{5\cdot 7}+\frac{1}{7\cdot 9}\amp =\frac{4}{9}
\end{align*}
Conjecture a general formula and prove it by mathematical induction.
2.
Evaluate the sum \(\sum_{i=1}^{n}\frac{i}{(i+1)!}\) for all \(n=1, 2, 3, 4, 5\text{.}\) Make a conjecture for a formula for the sum for a general \(n\text{,}\) and prove your conjecture by induction.
3.
Use mathematical induction to prove \(5^n-1\) is divisible by 4, for integers \(n\geq 0\text{.}\)
4.
Use mathematical induction to prove \(7^n-1\) is divisible by 6, for integers \(n\geq 0\text{.}\)
5.
Use mathematical induction to prove \(2^n<(n+1)!\text{,}\) for integers \(n\geq 2\text{.}\)
6.
Use mathematical induction to prove \(1+nx\leq (1+x)^n\text{,}\) for all real numbers \(x>-1\) and integers \(n\geq 2\text{.}\)
Hint.
You can only do induction on integers, and only one integer at a time. So in this problem you want to do induction on \(n\text{,}\) not \(x\text{.}\) Let \(x\) just be a variable. This problem does require \(x>-1\text{,}\) so make sure you indicate in your proof where you needed to use that condition.
You have attempted of activities on this page.
