More uses of induction and common mistakes

Induc­tion is not only for sums, divis­i­bil­ity and inequal­i­ties. When­ever a state­ment about $n$ can be built up one step at a time, induc­tion is the nat­ural tool: sequences defined by a rule link­ing each term to the one before, long prod­ucts, and count­ing prob­lems. This les­son shows a few of these uses, then looks at the mis­takes that turn an induc­tion "proof" into non­sense.

Sequences defined step by step#

When a sequence is given by a recur­sive rule, the usual approach is: work out the first few terms, guess a for­mula, then prove the guess by induc­tion.

Exam­ple 1#

A sequence has $a_1 = 1$ and $a_{n+1} = 2a_n + 1$. Find a for­mula for $a_n$ and prove it.

The first terms are $1, 3, 7, 15, 31$. Each is one less than a power of 2: $2 - 1$, $4 - 1$, $8 - 1$, $16 - 1$, $32 - 1$. So we guess $a_n = 2^n - 1$.

Base step. $a_1 = 1 = 2^1 - 1$. True.

Hypoth­e­sis. Assume $a_k = 2^k - 1$.

Induc­tive step. By the rule, $a_{k+1} = 2a_k + 1 = 2(2^k - 1) + 1 = 2^{k+1} - 2 + 1 = 2^{k+1} - 1$. This is the for­mula for $n = k + 1$.

By induc­tion, $a_n = 2^n - 1$ for every nat­ural num­ber $n$.

Exam­ple 2#

A sequence has $a_1 = 2$ and $a_{n+1} = a_n + 2n$. Prove that $a_n = n^2 - n + 2$.

Base step. $1 - 1 + 2 = 2 = a_1$. True.

Hypoth­e­sis. Assume $a_k = k^2 - k + 2$.

Induc­tive step. $a_{k+1} = a_k + 2k = k^2 - k + 2 + 2k = k^2 + k + 2$. The for­mula for $n = k + 1$ gives $(k + 1)^2 - (k + 1) + 2 = k^2 + 2k + 1 - k - 1 + 2 = k^2 + k + 2$. They agree.

By induc­tion the for­mula holds for all $n$.

Prod­ucts#

For a prod­uct of $n$ fac­tors, the prod­uct of $k + 1$ fac­tors is the prod­uct of $k$ fac­tors times one more fac­tor.

Exam­ple 3#

Prove that $\displaystyle \left(1 + \frac{1}{1}\right)\left(1 + \frac{1}{2}\right)\left(1 + \frac{1}{3}\right) \cdots \left(1 + \frac{1}{n}\right) = n + 1$.

Base step. For $n = 1$: $1 + 1 = 2$. True.

Hypoth­e­sis. Assume the prod­uct of the first $k$ fac­tors is $k + 1$.

Induc­tive step. Mul­ti­ply by the next fac­tor $\displaystyle 1 + \frac{1}{k + 1} = \frac{k + 2}{k + 1}$:

$$\displaystyle (k + 1) \times \frac{k + 2}{k + 1} = k + 2$$

which is the for­mula for $n = k + 1$. By induc­tion the result holds for all $n$.

Exam­ple 4#

Prove that $\displaystyle \left(1 - \frac{1}{2^2}\right)\left(1 - \frac{1}{3^2}\right) \cdots \left(1 - \frac{1}{n^2}\right) = \frac{n + 1}{2n}$ for every $n \ge 2$.

Base step. For $n = 2$: $\displaystyle 1 - \frac{1}{4} = \frac{3}{4}$, and $\displaystyle \frac{2 + 1}{4} = \frac{3}{4}$. True.

Hypoth­e­sis. Assume the prod­uct up to $\displaystyle 1 - \frac{1}{k^2}$ is $\displaystyle \frac{k + 1}{2k}$, for some $k \ge 2$.

Induc­tive step. The next fac­tor is $\displaystyle 1 - \frac{1}{(k + 1)^2} = \frac{(k + 1)^2 - 1}{(k + 1)^2} = \frac{k(k + 2)}{(k + 1)^2}$. So the prod­uct becomes

$$\displaystyle \frac{k + 1}{2k} \times \frac{k(k + 2)}{(k + 1)^2} = \frac{k + 2}{2(k + 1)}$$

which is the for­mula for $n = k + 1$. By induc­tion the result holds for all $n \ge 2$.

Count­ing#

Exam­ple 5#

Prove that a con­vex poly­gon with $n$ sides has $\displaystyle \frac{n(n - 3)}{2}$ diag­o­nals, for every $n \ge 3$.

Base step. A tri­an­gle has no diag­o­nals, and $\displaystyle \frac{3 \times 0}{2} = 0$. True.

Hypoth­e­sis. Assume a con­vex poly­gon with $k$ sides has $\displaystyle \frac{k(k - 3)}{2}$ diag­o­nals.

Induc­tive step. Make a poly­gon with $k + 1$ sides by adding one new cor­ner $V$ just out­side one side $AB$ of a $k$-sided poly­gon, and join­ing it to $A$ and $B$. Every old diag­o­nal is still a diag­o­nal. The side $AB$ now becomes a diag­o­nal too: 1 more. And $V$ can be joined to each of the other $k - 2$ old cor­ners: $k - 2$ more. So the num­ber of diag­o­nals is

$$\displaystyle \frac{k(k - 3)}{2} + 1 + (k - 2) = \frac{k^2 - 3k + 2k - 2}{2} = \frac{k^2 - k - 2}{2} = \frac{(k + 1)(k - 2)}{2}$$

which is the for­mula for $n = k + 1$. By induc­tion the result holds for all $n \ge 3$. For exam­ple, a hexa­gon has $\displaystyle \frac{6 \times 3}{2} = 9$ diag­o­nals.

Com­mon mis­takes#

1. Skip­ping the base step. As we saw in the first les­son, the step "$P(k) \implies P(k + 1)$" can be true for a state­ment that is false for every $n$. Always check the start­ing case.

2. Assum­ing what you want to prove. In the induc­tive step you assume $P(k)$, never $P(k + 1)$. A com­mon slip is to write down $P(k + 1)$, do the same thing to both sides until some­thing true appears, and stop. That shows only that $P(k + 1)$ leads to some­thing true, not that $P(k + 1)$ is true. Work from one side of $P(k + 1)$ to the other.

3. A step that does not work for every $k$. Here is a famous false "proof" that all the stu­dents in any group have the same height.

Base: in a group of 1 stu­dent, every­one has the same height. Step: sup­pose any group of $k$ stu­dents all have the same height, and take a group of $k + 1$. Send out one stu­dent; the remain­ing $k$ all have the same height. Bring that stu­dent back and send out another; again the remain­ing $k$ have the same height. The two groups over­lap, so all $k + 1$ have the same height.

The mis­take is in the step from $k = 1$ to $k + 1 = 2$. With two stu­dents, send­ing out one leaves one, and send­ing out the other leaves the other: the two smaller groups do not over­lap at all, so noth­ing links their heights. The step fails for $k = 1$, and so the whole chain of domi­noes never starts mov­ing. The induc­tive step must work for every $k$ from the start­ing value on.

Prac­tice#

1. A sequence has $a_1 = 3$ and $a_{n+1} = a_n + 4$. Prove that $a_n = 4n - 1$.
2. A sequence has $a_1 = 1$ and $a_{n+1} = 3a_n + 2$. Find $a_2$, $a_3$, $a_4$, and prove that $a_n = 2 \cdot 3^{n-1} - 1$.
3. Prove that $\displaystyle \left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right) \cdots \left(1 - \frac{1}{n + 1}\right) = \frac{1}{n + 1}$.
4. Prove that $\displaystyle \left(1 + \frac{3}{1}\right)\left(1 + \frac{5}{4}\right)\left(1 + \frac{7}{9}\right) \cdots \left(1 + \frac{2n + 1}{n^2}\right) = (n + 1)^2$.
5. The tri­an­gu­lar num­bers are $1, 3, 6, 10, \ldots$, with $n$th term $\displaystyle \frac{n(n + 1)}{2}$. Prove that the sum of the first $n$ of them is $\displaystyle \frac{n(n + 1)(n + 2)}{6}$.
6. In a group of $n$ peo­ple ($n \ge 2$), each pair shakes hands once. Prove by induc­tion that there are $\displaystyle \frac{n(n - 1)}{2}$ hand­shakes.
7. Some­one claims $\displaystyle 1 + 2 + \cdots + n = \frac{n^2 + n + 2}{2}$ and shows that if it is true for $k$ then it is true for $k + 1$. Check this step, then explain what is wrong with the claim.
8. How many diag­o­nals does a poly­gon with 12 sides have?

Answers#