Mathematical Induction

Name:

Class:

Date:

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
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$ ?
3.
Check $1 + 3 + 5 + \dots + (2n-1) = n^2$ for $n = 6$ : what is $1 + 3 + 5 + 7 + 9 + 11$ ?
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
5.
Before proving $2^n > n$ , check the first dominoes: compute $2^n$ for $n = 1, 2, 3$ .
6.
Check the formula $1 + 2 + 4 + \dots + 2^n = 2^{n+1} - 1$ for $n = 3$ .
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?
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$ .
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$
10.
Follow the inductive step for $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$ with numbers, using $k = 4$ .
11.
Follow the inductive step for $1 + 3 + \dots + (2n-1) = n^2$ with numbers, using $k = 6$ .
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$
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$ .
14.
By induction one can also prove that $n^3 - n$ is divisible by $6$ . For $n = 6$ , compute $\dfrac{6^3 - 6}{6}$ .
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
16.
Follow the inductive step for $1 + 2 + \dots + 2^n = 2^{n+1} - 1$ with numbers, using $k = 5$ .
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$ .
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.