Please Login to access more options.
Problem 33: (First Induction Problem)
For each $n\in \mathbb{N}$ consider the statement $$1+2+\cdots+n=\frac{n(n+1)}{2}.$$ This is infinitely many statements. How do we prove infinitely many statements are true? What follows is a proof that all of these statements are true. The proof relies on the domino problem done earlier in the semester. Part way through the proof are several different versions of how to proceed. Your job is to read the proof and the different versions, and then decide for each version if it is logically sound and clear.
| Option | Logically Sound (Y/N) | Clear (Y/N) |
|---|---|---|
| 1 | ||
| 2 | ||
| 3 | ||
| 4 | ||
| 5 | ||
| 6 |
We'll have a discussion in class about your answers. Now for the proof.
To simplify our writing below, for each $n\in \mathbb{N}$ let $S_n$ be the statement $$1+2+\cdots+n=\frac{n(n+1)}{2}.$$ We will prove that for each $n\in \mathbb{N}$, we know that $S_n$ is a true statement. To do this, we'll refer to the domino problem we proved earlier in the semester. Imagine for a minute that we have an infinite collection of dominos numbered $1, 2, 3, \ldots$. The first domino has the statement $1=\frac{1(2)}{2}$ on it, the second domino has the statement $1+2=\frac{2(3)}{2}$ on it, the third domino has the statement $1+2+3=\frac{3(4)}{2}$ on it, and so on. For each $n\in \mathbb{N}$, domino $n$ has the statement $S_n$ on it. We now have an infinite collection of dominos, one for each natural number $n$. We will now knock over each domino when we know the statement written on that domino is true. If we can knock over every domino, then $S_n$ is true for every $n\in \mathbb{N}$.
In the domino problem, two important things happened. First, note that Jon knocked over the first domino. Second, we knew that "if the $k$th domino falls, then it knocks over the $(k+1)$st domino." We will verify these two facts are true about our dominos. The first domino clearly falls, as the statement on the first domino is $1=\frac{1(2)}{2}$, which is true. We now must prove the second condition is true, namely "if the $k$th domino falls, then it knocks over the $(k+1)$st domino."
Option 1: Click to expand.
For each $k\in \mathbb{N}$ suppose domino $k$ fell. This means statement $S_k$ is true, which means $1+2+\cdots+k=\frac{k(k+1)}{2}$ is true. We then compute $$ \begin{align} \underbrace{1+2+3+\cdots + k} + (k+1) &=\frac{k(k+1)}{2}+(k+1) && \text{ (replace using the assumption) }\\ &=(k+1)\left[\frac{k}{2}+1\right] &&\text{ (factor) }\\ &=\frac{(k+1)(k+2)}{2} &&\text{(get a common denominator).} \end{align} $$ This proves that $1+2+\cdots+k+(k+1)=\frac{ (k+1) ( (k+1)+1) }{2}$, which means $S_{k+1}$ is a true statement. This shows that if statement $S_k$ is true, then statement $S_{k+1}$ must be true as well.
Option 2: Click to expand.
Suppose for some $k\in \mathbb{N}$ that domino $k$ fell. This means statement $S_k$ is true, which means $1+2+\cdots+k=\frac{k(k+1)}{2}$ is true. We then compute $$ \begin{align} \underbrace{1+2+3+\cdots + k} + (k+1) &=\frac{k(k+1)}{2}+(k+1) && \text{ (replace using the assumption) }\\ &=\frac{k^2+3k+2}{2} &&\text{ (get a common denominator) }\\ &=\frac{ (k+1)(k+2) }{2} &&\text{(factor).} \end{align} $$ This proves that $1+2+\cdots+k+(k+1)=\frac{ (k+1) ( (k+1)+1) }{2}$, which means $S_{k+1}$ is a true statement. This shows that if statement $S_k$ is true, then statement $S_{k+1}$ must be true as well.
Option 3: Click to expand.
Suppose that domino $k$ fell where $k\in \mathbb{N}$. This means statement $S_k$ is true, which means $1+2+\cdots+k=\frac{k(k+1)}{2}$ is true. We then compute $$ \begin{align} \underbrace{1+2+3+\cdots + k} + (k+1) &=\frac{k(k+1)}{2}+(k+1) && \text{ (replace using the assumption) }\\ &=(k+1)\left[\frac{k}{2}+1\right] &&\text{ (factor) }\\ &=\frac{ (k+1)(k+2) }{2} &&\text{(get a common denominator).} \end{align} $$ This proves that $1+2+\cdots+k+(k+1)=\frac{ (k+1) ( (k+1)+1) }{2}$, which means $S_{k+1}$ is a true statement. This shows that if statement $S_k$ is true, then statement $S_{k+1}$ must be true as well.
Option 4: Click to expand.
For each $k\in \mathbb{N}$ suppose domino $k$ fell. This means statement $S_k$ is true, which means $1+2+\cdots+k=\frac{k(k+1)}{2}$ is true. Since this assumption is true for every $k\in\mathbb{N}$, it must also be true when we look at the integer $k+1$. This means that statement $S_{k+1}$ is true, which means domino $k+1$ fell as needed. This shows that if statement $S_k$ is true, then statement $S_{k+1}$ must be true as well.
Option 5: Click to expand.
Suppose for some $k\in \mathbb{N}$ that domino $k$ fell. This means statement $S_k$ is true, which means $1+2+\cdots+k=\frac{k(k+1)}{2}$ is true. We must prove that statement $S_{k+1}$ is true, which means we must prove $$1+2+\cdots+k+(k+1)=\frac{ (k+1) ( (k+1)+1) }{2}.$$ We can replace the $1+2+\cdots +k$ with $\frac{k(k+1)}{2}$ in the above equation to get $$\frac{k(k+1)}{2}+(k+1)=\frac{ (k+1) ( (k+1)+1) }{2}.$$ The left side simplifies to $\frac{k(k+1)}{2}+(k+1)=\frac{k^2+k+2k+2}{2}=\frac{k^2+3k+2}{2}$. The right side simplifies to $\frac{ (k+1) ( (k+1)+1) }{2} = \frac{ (k+1) (k+2) }{2} =\frac{k^2+3k+2}{2}.$ Since the left and right side both simplify to the same thing, then the original statement $S_{k+1}$ is true. This shows that if statement $S_k$ is true, then statement $S_{k+1}$ must be true as well.
Option 6: Click to expand.
Suppose for some $k\in \mathbb{N}$ that domino $k$ fell. This means statement $S_k$ is true, which means $1+2+\cdots+k=\frac{k(k+1)}{2}$ is true. We must prove that statement $S_{k+1}$ is true, which means we must prove $$1+2+\cdots+k+(k+1)=\frac{ (k+1) ( (k+1)+1) }{2}.$$ Because we know $1+2+\cdots +k=\frac{k(k+1)}{2}$ (from our assumption that $S_{k}$ is true), substitution shows that statement $S_{k+1}$ is equivalent to the statement $$\frac{k(k+1)}{2}+(k+1)=\frac{ (k+1) ( (k+1)+1) }{2}.$$ The left side of the above equation is equal to $\frac{k(k+1)}{2}+(k+1)=\frac{k^2+k+2k+2}{2}=\frac{k^2+3k+2}{2}$. This means that statement $S_{k+1}$ is equivalent to $$\frac{k^2+3k+2}{2}=\frac{ (k+1) ( (k+1)+1) }{2}.$$ This last statement is clearly true as $ (k+1) ( (k+1)+1) = (k+1)(k+2)=k^2+3k+2$. This completes the proof that statement $S_{k+1}$ is true. This shows that if statement $S_k$ is true, then statement $S_{k+1}$ must be true as well.
We conclude by referring to the domino problem. Since the first domino was knocked over, and since the $k$th domino falling implies the $(k+1)$st domino falls, then we know that every domino falls (the conclusion of the domino problem). This means that $S_n$ is a true statement for every $n\in\mathbb{N}$.
The following pages link to this page.
Here are the old pages.