Skip to main content

PLP An introduction to mathematical proof

Seçkin Demirbaş, Andrew Rechnitzer

Section 7.2 More general inductions

Subsection 7.2.1 A little more general

There was nothing special about starting at \(n=1\) in our proof-sketch of the principle of mathematical induction. All that was required was that we could find the smallest integer in a set of natural numbers. We can quite readily generalise the proof to other sets of integers — as long as we can find the smallest integer in that set. So for example, instead of considering \(P(n)\) for all natural numbers \(n\text{,}\) we could consider \(P(n)\) for all integer \(n \geq -3\text{,}\) or all integers \(n \geq 7\) and so forth.
🔗
This idea leads to a slightly more general form of mathematical induction. The only differences are that the base case need not be at \(n=1\text{,}\) and that the inductive step must now be true for all integer \(k\) starting from the value in the base case. This is sometimes called extended mathematical induction.
🔗
We should put this theorem to work:
🔗
The proof of this result is nearly the same as our previous induction proofs; it consists of a basis case and an inductive step. The difference is that the basis step starts at \(n=5\text{.}\)
  • When \(n=5\) the inequality is \(2^5=32 \geq 5^2=25\text{,}\) which is true.
    🔗
  • For the inductive step we need to prove that
    \begin{align*} \left( 2^k \gt k^2 \right) & \implies \left( 2^{k+1} \gt (k+1)^2 \right) \end{align*}
    So we assume the first inequality, \(2^k \gt k^2\text{,}\) and have to work our way to the second, \(2^{k+1} \gt (k+1)^2\text{.}\) Multiplying the original inequality by 2 might be a good place to start.
    \begin{gather*} 2 \cdot 2^k = 2^{k+1} \gt 2k^2 \end{gather*}
    So we need to show that \(2k^2 \geq (k+1)^2\) or \(k^2 \geq 2k+1\text{.}\) Well since \(k\geq 5\) we have \(k^2 \geq 5k = 2k + 3k\) and since \(k \gt 1\text{,}\) \(3k \gt 1\) and we are done.
    🔗
Now we can write it up nicely.
🔗

Proof.

We proceed by induction.
  • Basis step — when \(n=5\) we have \(2^5=32 \gt 5^2=25\text{.}\) Hence the statement is true for \(n=5\text{.}\)
    🔗
  • Inductive hypothesis — assume \(2^k \gt k^2\text{.}\) Then \(2^{k+1}=2 \cdot 2^k \gt 2k^2\text{.}\) Since \(k \geq 5\) we have \(k^2 \geq 5k\text{,}\) and hence
    \begin{equation*} 2^{k+1} \gt 2k^2 = k^2+k^2 \geq k^2+5k = k^2 +2k +3k. \end{equation*}
    Now since \(k \geq 5\text{,}\) we know that \(3k>1\text{,}\) and so
    \begin{equation*} 2^{k+1} \gt k^2 + 2k +1 = (k+1)^2 \end{equation*}
    Thus if \(P(k)\) is true then \(P(k+1)\) is true.
    🔗
By the principle of mathematical induction the statement is true for all \(n\geq5\text{.}\)
🔗
🔗
It’s not a discussion of induction without some summation example.
🔗

Proof.

We prove this by induction. When \(n=a\) we have \(\frac{(a+a)(a+1-a)}{2} = a\) as required, so the base case holds.
🔗
Now assume that the result holds for \(n=k\text{.}\) Hence
\begin{align*} a + (a+1) + \cdots + k \amp = \frac{(k+a)(k+1-a)}{2} \amp \text{and so}\\ a + (a+1) + \cdots + k + (k+1) \amp = \frac{(k+a)(k+1-a)}{2} + (k+1) \\ \amp = \frac{1}{2}\left( k^2+3k+2 + a-a^2\right) \\ \amp = \frac{1}{2}\left( k+1+a )(k+2-a) \right) \end{align*}
as required. Since both the base case and induction step hold, the result follows by induction.
🔗
🔗
Here is another inequality result
🔗

Proof.

We prove the result by induction. When \(n=4\) we have
\begin{equation*} 4! = 24 \gt 16 = 2^4 \end{equation*}
so the base case is true.
🔗
Let us now assume that \(k! \gt 2^k\text{.}\) Then
\begin{align*} k! \amp\gt 2^k \\ (k+1) k! \amp \gt (k+1)2^k \\ (k+1)! \amp \gt (2 + (k-1))2^k \\ \amp = 2^{k+1} + (k-1)2^k \gt 2^{k+1} \end{align*}
where we have used the fact that \((k+1) \gt 0\) and \((k-1) \geq 0\text{.}\)
🔗
Since both the base case and induction hypothesis are true, the result follows by the principle of mathematical induction.
🔗
🔗
These inequality induction problems tend to be the most tricky of these 3 standard induction questions. Induction has its uses way beyond summation, divisibility and inequalities. Here are some more diverse examples.
🔗

Proof.

We prove this result by induction. When \(n=3\text{,}\) the result holds (as was stated above) with the set \(\set{2,3,6}\text{.}\)
🔗
Now assume the result holds for \(n=k\text{.}\) Hence there is a set \(\set{a_1,a_2,\cdots,a_k}\) so that
\begin{equation*} 1 = \frac{1}{a_1} + \frac{1}{a_2} + \cdots + \frac{1}{a_k} \end{equation*}
Notice two things. First, none of the \(a_i\) can be one, because otherwise the sum would be too large. Second, by dividing by two we get
\begin{equation*} \frac{1}{2} =\frac{1}{2a_1} + \frac{1}{2a_2} + \cdots + \frac{1}{2a_k} \end{equation*}
So we can make a new set of \(k+1\) numbers \(\set{2, 2a_1, 2a_2, \dots, 2a_k}\) so that the sum of their reciprocals is
\begin{equation*} \frac{1}{2} + \underbrace{\frac{1}{2a_1} + \frac{1}{2a_2} + \cdots + \frac{1}{2a_k}}_{=\frac{1}{2}} = 1 \end{equation*}
as required.
🔗
Since the base case is true, and the induction hypothesis is true, the result follows by mathematical induction.
🔗
Note that instead of dividing everything by two, one could also “split” the largest number in the set via
\begin{equation*} \frac{1}{x} = \frac{1}{1+x} + \frac{1}{x(x+1)}, \end{equation*}
since
\begin{equation*} \frac{1}{1+x} + \frac{1}{x(x+1)} = \frac{x}{x(1+x)}+ \frac{1}{x(x+1)} = \frac{x+1}{x(x+1)} = \frac{1}{x}. \end{equation*}
🔗
🔗

Aside: Egyptian fractions.

The next two examples are calculus-flavoured and so we assume some understanding
 79 
That is, some standard results from typical Calculus-1 and -2 courses on differential and integral calculus.
of results on derivatives and integrals. Those ideas are not covered in this text (except as a way of constructing some nice examples and exercises).
🔗

Proof.

We prove the result by induction. Let \(f\) be as defined in the statement of the result.
🔗
First note that
\begin{align*} f(x) \amp= x\log x \\ f'(x)\amp= 1 + \log x \\ f''(x)\amp= \frac{1}{x} \end{align*}
and hence the result holds for \(n=2\text{.}\)
🔗
Assume the result holds for \(n=k\text{,}\) then
\begin{align*} \diff{}{x} f^{(k)}(x) \amp = \diff{}{x}(-1)^k \frac{(k-2)!}{x^{k-1}} \\ \amp= (-1)^k (k-2)! \cdot(-1) (k-1)x^{-k} \\ \amp = (-1)^{k+1} \frac{(k-1)!}{x^k} \end{align*}
as required. Since the base case and inductive step hold, the result follows by induction.
🔗
🔗
To prove this result we’ll make use of the following fact (which you probably covered in a calculus course).
🔗

Proof of Result 7.2.7.

We prove this by induction.
  • When \(n=0\) we have
    \begin{align*} \int_0^\infty e^{-x} \dee{x} \amp= \left[ -e^{-x} \right]_0^\infty\\ \amp = 1 - \lim_{b \to \infty}e^{-b}\\ \amp = 1 - 0 = 1 = 0! \end{align*}
    where we have used Fact 7.2.8 to evaluate the limit. Hence the base case is true.
    🔗
    🔗
  • Assume that the result holds for \(n=k\text{.}\) Then we evaluate the integral for \(n=k+1\) using integration by parts.
    \begin{align*} \int_0^\infty x^{k+1} e^{-x}\dee{x} \amp = \left[ -e^{-x}x^{k+1}\right]_0^\infty + \int_0^\infty (k+1)x^k e^{-x}\dee{x}\\ \amp = (k+1) \int_0^\infty x^k e^{-x} \dee{x} + 0 - \lim_{b\to 0} e^{-x}x^{k+1}\\ \amp = (k+1) \int_0^\infty x^k e^{-x} \dee{x}\\ \amp = (k+1) k! = (k+1)! \end{align*}
    as required. Again we have used Fact 7.2.8 to evaluate the limits.
    🔗
    🔗
By the principle of mathematical induction, the result holds for all \(n \geq 0\text{.}\)
🔗
🔗
🔗

Subsection 7.2.2 More general and yet equivalent

We can generalise induction yet further with a stronger hypothesis in the induction step. In particular, we can set up induction so that we use all of the earlier statements \(P(\ell), \cdots, P(k)\) to prove the next \(P(k+1)\text{.}\) This stronger hypothesis gives the result its name, rather than the actual result being stronger. We have called this a corollary because one can prove it from regular induction (and we will). In fact, it is equivalent to regular induction, which we can show by proving regular induction from strong induction.
🔗

Proof.

As always, we start by assuming the hypotheses are true and work our way to the conclusion. So assume that \(P(\ell)\) is true, and that \(P(\ell) \land P(\ell+1) \land \cdots \land P(k) \implies P(k+1)\) is true for all \(k \in S\text{.}\)
🔗
To use regular induction we use a little trick. Let \(Q(n)\) be the statement
\begin{equation*} P(\ell), P(\ell+1), \cdots, P(n) \text{ are all true} \end{equation*}
Then since \(P(1)\) is true, we know that \(Q(1)\) is true. Further, since we know that
\begin{equation*} P(\ell) \land P(\ell+1) \land \cdots \land P(k) \implies P(k+1) \end{equation*}
then if \(Q(k)\) is true, then \(Q(k+1)\) is true. Hence \(Q(k) \implies Q(k+1)\) is true. By (regular) mathematical induction, we know that \(Q(n)\) is true for all \(n \in S\text{,}\) and so \(P(n)\) is true for all \(n \in S\) as required.
🔗
🔗
We can actually go further and prove that strong induction implies regular induction. This proves that the two types of induction are actually equivalent to each other. Anything you can prove with one, you can prove with the other; though that does not say the proofs would be equally appealing.
🔗

Proof.

We are actually proving here that Strong Induction (Corollary 7.2.9) if and only if Mathematical Induction (Theorem 7.2.1). We have already proved that regular induction implies strong induction in the proof of Corollary 7.2.9, so it is sufficient for us to prove that strong induction implies regular induction.
🔗
Assume the hypothesis of regular induction. That is \(P(\ell)\) is true and \(P(k) \implies P(k+1)\) for any \(k\in S\text{.}\) Again a small trick can be used:
\begin{equation*} P(\ell)\land P(\ell+1)\land \cdots \land P(k) \implies P(k) \end{equation*}
The only way the above can be false is if the hypothesis is true but the conclusion is false. That cannot happen because \(P(k)\) appears in the conjunction of the hypothesis (and so must be true) and as the conclusion. Put this above together with the assumption \(P(k) \implies P(k+1)\text{:}\)
\begin{equation*} P(\ell)\land P(\ell+1)\land \cdots \land P(k) \implies P(k) \implies P(k+1) \end{equation*}
and we have satisfied the hypotheses of strong induction. Hence \(P(n)\) is true for all \(n \in S\text{.}\)
🔗
🔗

Proof.

We prove this by strong induction.
  • When \(n=12\text{,}\) we can set \(a=4,b=0\text{.}\) Then since \(12=3\times 4\) the result holds.
    🔗
  • The inductive step is simpler if we also show that the result holds for \(n=13,14\text{.}\) In particular since \(13=2\times 3 +7\) and \(14 = 2\times 7\text{,}\) the result is true for \(n=12,13,14\text{.}\)
    🔗
  • Now assume that the result holds for all \(n=12,13,14\dots,k\text{,}\) with \(k\geq 14\text{,}\) and so we can write \(k-2 = 3a + 7b\text{.}\) Then it follows that \(k+1 = 3+(k-2) = 3(a+1)+7b\) and so has the required form. That is, since the result holds for all \(n=12,\dots,k\text{,}\) we know that it holds for \(n=k+1\text{.}\)
    🔗
So by strong induction, the result holds for all integer \(n \geq 12\text{.}\)
🔗
🔗

Proof.

To simplify the discussion, let \(q_n\) denote \(z^n + z^{-n}\text{.}\) By assumption we have that \(q_1 \in \mathbb{Z}\text{.}\) Further note that \(q_{-n} = q_n\) so it is sufficient to prove that \(q_n \in \mathbb{Z}\) for all integer \(n \geq 0\text{;}\) we do so by induction.
🔗
When \(n=0\text{,}\) we have
\begin{equation*} z^0 + z^{-0} = q_0 = 2 \in \mathbb{Z} \end{equation*}
so the result holds.
🔗
Now assume that the result holds for \(0 \leq n \leq k\text{.}\) So we know that \(q_1, q_{k-1}, q_k\) are integers. Hence
\begin{align*} q_k q_1 \amp = (z^k + z^{-k})(z+z^{-1})\\ \amp= z^{k+1} + z^{k-1} + z^{1-k} + z^{-k-1}\\ \amp = \underbrace{z^{k-1}+z^{1-k}}_{=q_{k-1}} + \underbrace{z^{k+1}+z^{-1-k}}_{=q_{k+1}} \end{align*}
So we have
\begin{equation*} q_{k+1} = q_k q_1 - q_{k-1} \end{equation*}
Since \(q_1,q_{k-1},q_k \in \mathbb{Z}\) we know that \(q_{k+1} \in \mathbb{Z}\) as required. The result then follows by mathematical induction.
🔗
🔗
A chocolate bar example.
🔗

Example 7.2.13. Breaking a bar of chocolate.

Say we have a bar of chocolate as shown below — a line of \(n\) blocks. Prove that it takes \(n-1\) breaks to split it into \(n\) individual pieces.
🔗
We prove this by strong induction.
  • First, when \(n=1\text{,}\) there is nothing to do; it takes 0 breaks to split it into \(1\) block. The result holds.
    🔗
  • Now assume that the result holds for bars of \(1,2,\dots,n\) blocks, and then consider a bar of \(n+1\) blocks. Say we split it into two pieces, one of size \(k\text{,}\) and one of size \(n+1-k\) (with \(k=1,2,\dots,n\)). This takes \(1\) break, and we are left with the problem of splitting up the bar of \(k\) blocks and the bar of \(n+1-k\) blocks (as shown below).
    🔗
    However, by assumption, we know that splitting a bar of \(k\) blocks takes \(k-1\) breaks, and splitting a bar of \(n+1-k\) blocks takes \(n-k\) breaks. So, in total we’ll need \(1 + k-1 + n-k = n\) breaks. Notice that this is independent of our choice \(k\text{.}\) Hence the result holds for a bar of \(n+1\) blocks.
    🔗
    🔗
By strong induction the result holds for all \(n\text{.}\)
🔗
A slightly higher dimensional analogue of this problem involves cutting a pizza using \(n\) straight slices. The interested reader should search-engine their way to the “lazy caterer sequence”, or (equivalently) the central polygonal numbers. Going up one more dimension one arrives at the “cake numbers” which define the number of chunks of cake you can make when slicing a cube with \(n\)-planes.
🔗
🔗
Here is a more gamey example.
🔗

Example 7.2.14. A game of taking away.

Let \(n\) be a natural number. Two players place \(n\) balls in a box. The players take turns removing either one, two or three balls from the box. The player that removes the last ball loses.
🔗
So for example, if there are 13 balls in the box, the game could play out as
  • Player 1 removes 3 balls, leaving 10
    🔗
  • Player 2 then removes 2 balls, leaving 8
    🔗
  • Player 1 removes another 3 balls, leaving 5
    🔗
  • Player 2 removes 2 balls, leaving 3
    🔗
  • Player 1 removes 2 balls leaving 1
    🔗
  • Player 2 now must remove the last ball and so loses the game.
    🔗
🔗
We can prove that if \(n \equiv 1 \mod 4\text{,}\) then Player 2 can always win (if they are careful). We prove this by strong induction.
🔗
When the game starts with \(n=1=4\times 0 +1\) balls, Player 1 must remove the only ball from box and so loses.
🔗
Now assume that Player 2 can always win when \(n=4\ell+1\) for \(n=1,5,\dots,4\ell+1\text{.}\) Now consider what happens when the box starts with \(n=4\ell+5\) balls. Since Player 2 knows how to win if they leave Player 1 with \(4\ell+1\) balls, they will respond to Player 1’s move by trying to get to \(4\ell+1\) balls.
  • If Player 1 removes 1 ball, then this gives \(4\ell+4\text{,}\) and so Player 2 takes 3 balls
    🔗
  • If Player 1 removes 2 balls, then this gives \(4\ell+3\text{,}\) and so Player 2 takes 2 balls
    🔗
  • If Player 1 removes 3 balls, then this gives \(4\ell+2\text{,}\) and so Player 2 takes 1 ball
    🔗
So, no matter what Player 1 does, Player 2 can choose their move so as to leave Player 1 with \(4\ell+1\) balls. From that point, by assumption, Player 2 has a winning strategy.
🔗
So by strong induction, Player 2 has a winning strategy whenever \(n=4\ell+1\text{.}\)
🔗
🔗
Here are a couple of examples involving the Fibonacci numbers. Even those these are well known we’ll take a moment to define them formally.
🔗

Definition 7.2.15.

The Fibonacci numbers are defined recursively
 80 
i.e. we give the first few Fibonacci numbers, and then we define later Fibonacci numbers in terms of earlier Fibonacci numbers.
by
\begin{equation*} F_0 = 0 \qquad F_1 = 1 \qquad F_{n+1} = F_n + F_{n-1}. \end{equation*}
The first few Fibonacci numbers are \(0,1,1,2,3,5,8,13,\dots\)
🔗
🔗
The Fibonacci numbers have many interesting properties and patterns. They also show up all over mathematics and one can find (via the reader’s favourite search engine) many examples of Fibonacci numbers in the “real world”. We’ll start off with an easy result that doesn’t require strong induction and then work up towards some harder ones.
🔗

Proof.

We prove this by induction. When \(n=1\) the statement becomes
\begin{equation*} F_1 = F_3-1 \end{equation*}
and since \(F_1=1, F_3=2\) it is true.
🔗
Now assume that the result holds for \(n=k\text{.}\) That is
\begin{equation*} F_1 + F_2 + \cdots + F_k = F_{k+2}-1 \end{equation*}
Then we have
\begin{align*} F_1 + F_2 + \cdots + F_k + F_{k+1} \amp= F_{k+1}+F_{k+2}-1 \\ \amp= F_{k+3}-1 \end{align*}
as required. Since both the base case and inductive step are true, the result follows by induction.
🔗
🔗

Proof.

We prove this by induction. When \(n=1\text{:}\)
\begin{equation*} F_2 F_0 - F_1^2 = 0 - 1 = -1 \end{equation*}
as required.
🔗
Now assume that it holds for \(n=k\text{,}\) so that
\begin{equation*} F_{k+1}F_{k-1} - F_k^2 = (-1)^k \end{equation*}
Now consider
\begin{align*} F_{k+2}F_k - F_{k+1}^2 \amp = (F_{k+1}+F_k)F_k - (F_k+F_{k-1})F_{k+1} \\ \amp= \underbrace{F_{k+1}F_k} + F_k^2 - \underbrace{F_kF_{k+1}} - F_{k-1}F_{k+1} \\ \amp= F_k^2 - F_{k-1}F_{k+1} \\ \amp = - (F_{k+1}F_{k-1} - F_k^2) \\ \amp = (-1)^{k+1} \end{align*}
as required. Since both the base case and inductive step hold, the result follows by induction.
🔗
🔗

Proof.

Fix \(q \in \mathbb{N}\text{.}\) We prove the result by induction. When \(n=1\) the result holds since \(F_5 = 5\text{.}\)
🔗
Now assume that \(5 \mid F_{5k}\text{.}\) Now
\begin{align*} F_{5k+5} \amp= F_{5k+4} + F_{5k+3} \\ \amp= (F_{5k+3}+F_{5k+2}) + F_{5k+3} = 2F_{5k+3}+F_{5k+2} \\ \amp= 2(F_{5k+2}+2F_{5k+1}) + F_{k+2} =3F_{5k+2}+2F_{5k+1} \\ \amp= 3(F_{5k+1}+F_{5k})+2F_{5k+1} = 5F_{5k+1}+3F_{5k} \end{align*}
Now since \(5\mid F_{5k}\) it follows that \(5 \mid F_{5k+5}\text{.}\) The result follows by induction.
🔗
🔗

Proof.

Induction is not the easiest way to prove these, but we will press on. The results hold when \(n=1\) since
\begin{align*} F_1 \amp = 1 = 1^2+ 0^2 = F_1^2 + F_0^2 \\ F_2 \amp = 1 = 1^2 - 0^2 = F_2^2 - F_0^2 \end{align*}
🔗
Now assume the result holds for all \(k \leq n\text{.}\) Now from the recurrence that defines the Fibonacci numbers:
\begin{align*} F_{2k+1} \amp = F_{2k}+F_{2k-1} \\ \amp= (F_{k+1}^2 - F_{k-1}^2) + (F_k^2 + F_{k-1}^2) \amp \text{by assumption} \\ \amp= F_{k+1}^2 + F_k^2 \end{align*}
as required. We do similarly for the other equation (though more gymnastics are required).
\begin{align*} F_{2k+2} \amp = F_{2k+1}+F_{2k} \\ \amp= (F_{k+1}^2 + F_k^2) + (F_{k+1}^2 - F_{k-1}^2) \end{align*}
Try to make the first bracket look like \(F_{k+2}^2 = (F_{k+1}+F_k)^2\)
\begin{align*} \amp= (F_{k+1}^2 \underbrace{+ 2F_{k+1}F_k}_{+} + F_k^2) + (F_{k+1}^2 - F_{k-1}^2) \underbrace{-2 F_k F_{k+1}}_{-} \end{align*}
Now manipulate the second bracket using difference of squares and then \(F_{k+1}-F_{k-1}=F_k\)
\begin{align*} \amp= (F_{k+1} + F_k)^2 + (F_{k+1}-F_{k-1})(F_{k+1}+F_{k-1})-2F_kF_{k+1}\\ \amp= F_{k+2}^2 + F_k (F_{k+1}+F_{k-1} -2 F_{k+1})\\ \amp= F_{k+2}^2 - F_k (F_{k+1} - F_{k-1})\\ \amp = F_{k+2}^2 - F_k^2 \end{align*}
as required.
🔗
Since the base case is true and the inductive step is true, the result follows by induction.
🔗
🔗
Next is an important example that proves every integer bigger than \(2\) can be written as a product of prime numbers. This statement is part of the Fundamental Theorem of Arithmetic, which also says that the product is unique. Proving uniqueness takes more work — see Section 9.6. This result focuses on proving the existence of at least one factorisation into primes.
🔗
This is also a really good example of a result that we all know, but we haven’t proved. When we do sit down to try to prove such results it can be easy to get confused or disoriented because the result seems so obvious; we’ve known and worked with the result for years! Some such results may indeed be trivial while some need more work. It is always a good idea to go back to the basic definitions and methods to help work your way to a proof.
🔗

Example 7.2.20. There exists a prime factorisation.

Let \(n\in\mathbb{N}\text{,}\) \(n\geq 2\text{.}\) Then \(n\) is a product of prime numbers.
🔗
Scratchwork.
Notice that the statement includes the case where \(n\) is prime, whence \(n\) is the product of a single prime — itself! Then, any integer greater than 2 is prime or not prime. If it is not prime, what can we say about its divisors?
🔗
Let’s try to prove the statement using induction on \(n\text{.}\) The base case should be \(n=2\text{.}\) In this case, the statement is true, since \(2\) is prime, and therefore a product of prime numbers (in this case, the product of a single prime number, \(2\)). Now suppose the result holds for \(n=k\text{,}\) so that \(n=k\) is a product of prime numbers. We need to show that \(k+1\) is a product of prime numbers. We can try to prove this by considering two cases: \(k+1\) is prime, or \(k+1\) is not prime, one of which must be true.
  • \(k+1\) is prime: then the result holds for \(n=k+1\text{,}\) so we’re done.
    🔗
    🔗
  • \(k+1\) is not prime: here we can’t conclude anything immediately. Instead we’ll try to use the inductive hypothesis to show that the result holds. By definition, \(k+1\) not being prime means that there are \(a,b\in\mathbb{N}\text{,}\) \(1 \lt a,b \lt k+1\text{,}\) such that \(k+1=ab\text{.}\)
    🔗
    Now, if we knew \(a\) and \(b\) could be written as a product of prime numbers, then we’d also have that \(k+1\) is a product of prime numbers. But we don’t know this, since for the inductive hypothesis, we only assumed that \(n=k\) could be written as a product of prime numbers. Indeed, it is not clear how we can get from \(n=k\) to \(n=k+1\) in our inductive step since \(k\) and \(k+1\) don’t share common factors other than \(\pm 1\) (see Exercise 3.5.7). This suggests that we use strong induction instead of regular induction.
    🔗
    🔗
🔗
Let’s try again using strong induction. The base case is the same as before. This time, for the inductive hypothesis, instead of just assuming that \(n=k\) is a product of prime numbers, we assume that for any \(2\leq n\leq k\text{,}\) \(n\) is a product of prime numbers. We need to show that \(k+1\) is a product of prime numbers. Again we can split this into two cases.
  • \(k+1\) is prime: then the result holds for \(n=k+1\text{,}\) so we’re done.
    🔗
    🔗
  • \(k+1\) is not prime: By definition, \(k+1\) not being prime means that there are \(a,b\in\mathbb{N}\text{,}\) \(1 \lt a,b \lt k+1\text{,}\) such that \(k+1=ab\text{.}\) By the inductive hypothesis, both \(a\) and \(b\) can be written as a product of prime numbers; that is \(a=p_1\cdots p_r\) and \(b=q_1\cdots q_s\) for prime numbers \(p_1,\dots,p_r,q_1,\dots,q_s\text{.}\) (Note that these prime numbers are not necessarily distinct, and if \(a\) or \(b\) were itself prime, then \(r=1\) or \(s=1\text{,}\) respectively.) Then
    \begin{equation*} k+1 = ab=p_1\cdots p_rq_1\cdots q_s \end{equation*}
    and so \(k+1\) may be written as a product of prime numbers.
    🔗
    🔗
In either case, we’ve concluded that \(k+1\) is a product of prime numbers, and so the inductive step is complete. Let’s write up our argument.
🔗
🔗
Solution.
Proof.
Let \(n\in\mathbb{N}\text{,}\) \(n\geq 2\text{.}\) We proceed by strong induction on \(n\text{.}\) For the base case, suppose \(n=2\text{.}\) Then \(n\) is prime, and the result holds.
🔗
Now suppose that the result holds for all \(2\leq n\leq k\text{;}\) that is, if \(n\leq k\text{,}\) then \(n\) is a product of prime numbers. Either \(k+1\) is prime, or not prime. If \(k+1\) is prime, then the result holds. So suppose that \(k+1\) is not prime. Then, by definition, \(k+1=ab\) for some \(a,b\in\mathbb{N}\text{,}\) \(1 \lt a,b \lt k+1\text{.}\) By the inductive hypothesis, both \(a\) and \(b\) can be written as a product of prime numbers; that is \(a=p_1\cdots p_r\) and \(b=q_1\cdots q_s\) for prime numbers \(p_1,\dots,p_r,q_1,\dots,q_s\text{.}\) Then
\begin{equation*} k+1 = ab=p_1\cdots p_rq_1\cdots q_s \end{equation*}
and so \(k+1\) may be written as a product of prime numbers. Thus the result holds for \(k+1\text{.}\) Thus by strong induction, any \(n\in\mathbb{N}\text{,}\) \(n\geq 2\) is a product of prime numbers.
🔗
🔗
🔗
🔗
Finally, a nice trigonometric example
 81 
We hope the reader didn’t think they could avoid trigonometry just because this isn’t a calculus text. Take this as a sine of how important the topic is (and its related puns).
. We’ll assume that you remember (or can quickly revise) the formulas
\begin{align*} \cos(a+b)\amp=\cos a \cos b - \sin a \sin b \\ \cos(a-b)\amp=\cos a \cos b + \sin a \sin b \end{align*}
🔗

Proof.

We prove the result by induction. When \(n=0\) we have \(p_0 = \cos 0 = 1\text{,}\) so the base case is true. We now turn to the inductive step.
🔗
Assume that the result hold for \(n=0,1,\cdots,k\text{.}\) In particular,
\begin{align*} p_1\amp=\cos\theta \amp p_k\amp=\cos k\theta \end{align*}
Now it suffices to show that \(p_{k+1} = 2p_1 p_k - p_{k-1} = \cos((k+1)\theta)\text{.}\) Substitute in the values of \(p_1, p_k, p_{k-1}\text{:}\)
\begin{equation*} p_{k+1} = 2\cos\theta \cos(k\theta) - \cos((k-1)\theta) \end{equation*}
Recall (from the formulas above) that
\begin{align*} \cos( (k+1)\theta ) \amp = \cos\theta \cos k\theta - \sin\theta\sin k\theta \amp \text{and}\\ \cos( (k-1)\theta ) \amp = \cos\theta \cos k\theta + \sin\theta\sin k\theta \end{align*}
so that
\begin{equation*} \cos((k+1)\theta ) + \cos((k-1)\theta) = 2\cos\theta\cos k\theta \end{equation*}
Substituting this into the expression for \(p_{k+1}\) above then gives
\begin{equation*} p_{k+1} = \cos((k+1)\theta) \end{equation*}
as required.
🔗
🔗
🔗
🔗
PrevTopNext