Mathematical Induction

Show your work for each problem.

1.
Which two parts must every proof by mathematical induction contain?
1. a)Only checking the cases $n = 1$ to $n = 5$
2. b)A counterexample and a contradiction
3. c)A base case and an inductive step
4. d)A table with statements and reasons
Answer: A base case and an inductive step
Every induction proof needs a base case (the first domino falls) and an inductive step (each falling domino knocks over the next). Checking a few cases is not a proof, and counterexamples or tables belong to other proof styles.
2.
The formula $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$ was proven by induction. Check it for $n = 5$ : what is $1 + 2 + 3 + 4 + 5$ ?
Answer: 15
$1 + 2 + 3 + 4 + 5 = 15$ and $\dfrac{5 \cdot 6}{2} = 15$ . The formula gives the same value.
3.
Check $1 + 3 + 5 + \dots + (2n-1) = n^2$ for $n = 6$ : what is $1 + 3 + 5 + 7 + 9 + 11$ ?
Answer: 36
$1 + 3 + 5 + 7 + 9 + 11 = 36 = 6^2$ , exactly as the formula predicts.
4.
In the domino picture of induction, what does the inductive step guarantee?
1. a)All dominoes have the same size
2. b)The first domino falls
3. c)Each falling domino knocks over the next one
4. d)The last domino falls
Answer: Each falling domino knocks over the next one
The inductive step proves $P(k) \Rightarrow P(k+1)$ : whenever one domino falls, the next one falls too. The first domino falling is the base case. There is no last domino, the row is endless.
5.
Before proving $2^n > n$ , check the first dominoes: compute $2^n$ for $n = 1, 2, 3$ .
Answer: 8
1. What is $2^1$ ? (base case, compare with $n = 1$ ) 2
2. What is $2^2$ ? (compare with $n = 2$ ) 4
3. What is $2^3$ ? (compare with $n = 3$ ) 8
6.
Check the formula $1 + 2 + 4 + \dots + 2^n = 2^{n+1} - 1$ for $n = 3$ .
Answer: 15
1. Compute the left side $1 + 2 + 4 + 8$ . 15
2. Compute $2^{3+1} = 2^4$ . 16
3. Compute the right side $2^4 - 1$ . 15
7.
Let $P(n)$ be $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$ . In the inductive step with $k = 9$ , the right side of $P(k+1)$ is $\dfrac{(k+1)(k+2)}{2}$ . What is its value?
Answer: 55
$\dfrac{10 \cdot 11}{2} = 55$ . Check: the hypothesis gives $1 + \dots + 9 = 45$ , and adding the next term $10$ gives $55$ .
8.
Use the formula $1 + 2 + 4 + \dots + 2^n = 2^{n+1} - 1$ , proven by induction, to compute $1 + 2 + 4 + 8 + 16 + 32 + 64$ .
Answer: 127
The last term is $2^6$ , so $n = 6$ and the sum is $2^7 - 1 = 128 - 1 = 127$ .
9.
In the inductive step for $1 + 3 + 5 + \dots + (2n-1) = n^2$ , which term is added to $1 + 3 + \dots + (2k-1)$ to get the left side of $P(k+1)$ ?
1. a) $2k + 1$
2. b) $k + 1$
3. c) $2k$
4. d) $2k - 1$
Answer: $2k + 1$
The last term of $P(k+1)$ is $2(k+1) - 1 = 2k + 1$ . The term $2k - 1$ is already in the sum, and $k + 1$ and $2k$ are not odd numbers of this pattern.
10.
Follow the inductive step for $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$ with numbers, using $k = 4$ .
Answer: 15
1. By the hypothesis, $1 + 2 + 3 + 4 = \dfrac{4 \cdot 5}{2}$ . What is it? 10
2. What is the next term $k + 1$ ? 5
3. Add it: what is the new sum $1 + 2 + 3 + 4 + 5$ ? 15
4. What does the formula give for $k + 1 = 5$ , that is $\dfrac{5 \cdot 6}{2}$ ? 15
11.
Follow the inductive step for $1 + 3 + \dots + (2n-1) = n^2$ with numbers, using $k = 6$ .
Answer: 49
1. By the hypothesis, the sum of the first $6$ odd numbers is $6^2$ . What is it? 36
2. What is the next odd number $2k + 1$ ? 13
3. Add it: what is the new sum? 49
4. What is $(k+1)^2 = 7^2$ ? 49
12.
Which sentence is the correct inductive hypothesis when proving $2^n > n$ for all $n \ge 1$ ?
1. a)Assume $2^n > n$ for all $n \ge 1$
2. b)Assume $2^k > k$ for some integer $k \ge 1$
3. c)Assume $2^{k+1} > k + 1$
4. d)Prove that $2^1 > 1$
Answer: Assume $2^k > k$ for some integer $k \ge 1$
The inductive hypothesis assumes the statement for one arbitrary $k$ . Assuming it for all $n$ or for $k + 1$ assumes what we want to prove, and $2^1 > 1$ is the base case.
13.
The inductive step for " $n^3 - n$ is divisible by $3$ " uses $(k+1)^3 - (k+1) = (k^3 - k) + 3k^2 + 3k$ . Check this with $k = 4$ .
Answer: 60
1. What is $k^3 - k$ for $k = 4$ ? 60
2. What is $(k+1)^3 - (k+1)$ for $k = 4$ ? 120
3. What is the difference $120 - 60$ ? 60
4. What is $3k^2 + 3k$ for $k = 4$ ? 60
14.
By induction one can also prove that $n^3 - n$ is divisible by $6$ . For $n = 6$ , compute $\dfrac{6^3 - 6}{6}$ .
Answer: 35
$6^3 - 6 = 216 - 6 = 210$ and $210 \div 6 = 35$ , a whole number, as the statement predicts.
15.
A student "proves" that $1 + 2 + \dots + n = \dfrac{n(n+1)}{2} + 1$ for all $n \ge 1$ . The algebra in the inductive step is correct. What is wrong?
1. a)The hypothesis must be $P(k+1)$ , not $P(k)$
2. b)Nothing, the statement is true
3. c)The base case fails: for $n = 1$ the left side is $1$ , the right side is $2$
4. d)Induction cannot be used for sums
Answer: The base case fails: for $n = 1$ the left side is $1$ , the right side is $2$
For $n = 1$ : the left side is $1$ , the right side is $\dfrac{1 \cdot 2}{2} + 1 = 2$ . The base case fails, so the chain never starts. In fact the claim is false for every $n$ , because the true sum is $\dfrac{n(n+1)}{2}$ .
16.
Follow the inductive step for $1 + 2 + \dots + 2^n = 2^{n+1} - 1$ with numbers, using $k = 5$ .
Answer: 127
1. By the hypothesis, $1 + 2 + \dots + 2^5 = 2^6 - 1$ . What is it? 63
2. What is the next term $2^{k+1} = 2^6$ ? 64
3. Add it: what is the new sum? 127
4. What is $2^{k+2} - 1 = 2^7 - 1$ ? 127
17.
The inductive step for $2^n > n$ uses the chain $2^{k+1} = 2 \cdot 2^k > 2k \ge k + 1$ . Follow it with $k = 5$ .
Answer: 6
1. What is $2^k = 2^5$ ? 32
2. What is $2^{k+1} = 2 \cdot 2^5$ ? 64
3. What is $2k$ ? 10
4. What is $k + 1$ ? 6
18.
The formula $1 \cdot 2 + 2 \cdot 3 + \dots + n(n+1) = \dfrac{n(n+1)(n+2)}{3}$ is proven by induction. Work through its base case and one inductive step with numbers.
Answer: 40
1. Base case: what is the right side for $n = 1$ , that is $\dfrac{1 \cdot 2 \cdot 3}{3}$ ? (The left side is $1 \cdot 2 = 2$ .) 2
2. Hypothesis for $k = 3$ : what is $\dfrac{3 \cdot 4 \cdot 5}{3}$ ? 20
3. What is the next term $(k+1)(k+2)$ for $k = 3$ ? 20
4. Add it to the hypothesis value. What is the new sum? (Compare with $\dfrac{4 \cdot 5 \cdot 6}{3}$ .) 40