Proof by induction — practice questions

Let $P(n)$ be the statement $\sum_{r=1}^{n} r(r+1) = \frac{1}{3}n(n+1)(n+2)$.

Step 1: Base Case We need to show $P(1)$ is true. For $n=1$, LHS = $\sum_{r=1}^{1} r(r+1) = 1(1+1) = 2$. RHS = $\frac{1}{3}(1)(1+1)(1+2) = \frac{1}{3}(1)(2)(3) = 2$. Since LHS = RHS, $P(1)$ is true.

Step 2: Inductive Hypothesis Assume that $P(k)$ is true for some positive integer $k$. That is, assume $\sum_{r=1}^{k} r(r+1) = \frac{1}{3}k(k+1)(k+2)$.

Step 3: Inductive Step We need to show that $P(k+1)$ is true. That is, we need to prove that $\sum_{r=1}^{k+1} r(r+1) = \frac{1}{3}(k+1)((k+1)+1)((k+1)+2) = \frac{1}{3}(k+1)(k+2)(k+3)$.

Consider the LHS for $n=k+1$: $\sum_{r=1}^{k+1} r(r+1) = \left( \sum_{r=1}^{k} r(r+1) \right) + (k+1)((k+1)+1)$ $= \left( \sum_{r=1}^{k} r(r+1) \right) + (k+1)(k+2)$

Now, using the inductive hypothesis for the sum up to $k$: $= \frac{1}{3}k(k+1)(k+2) + (k+1)(k+2)$

Factor out the common terms $(k+1)(k+2)$: $= (k+1)(k+2) \left( \frac{1}{3}k + 1 \right)$ $= (k+1)(k+2) \left( \frac{k+3}{3} \right)$ $= \frac{1}{3}(k+1)(k+2)(k+3)$

This is the required RHS for $P(k+1)$. So, if $P(k)$ is true, then $P(k+1)$ is true.

Step 4: Conclusion Since $P(1)$ is true, and it has been shown that if $P(k)$ is true then $P(k+1)$ is true, by the principle of mathematical induction, the statement is true for all positive integers $n$.

Let $P(n)$ be the statement '$7^n - 1$ is divisible by 6'.

Step 1: Base Case For $n=1$, $f(1) = 7^1 - 1 = 6$. Since 6 is divisible by 6, $P(1)$ is true.

Step 2: Inductive Hypothesis Assume that $P(k)$ is true for some integer $k \ge 1$. This means we assume $7^k - 1$ is divisible by 6. So, we can write $7^k - 1 = 6m$ for some integer $m$. This implies $7^k = 6m + 1$.

Step 3: Inductive Step We want to prove that $P(k+1)$ is true, i.e., that $7^{k+1} - 1$ is divisible by 6. Consider $f(k+1) = 7^{k+1} - 1$. $f(k+1) = 7 \cdot 7^k - 1$

Now, substitute the expression for $7^k$ from our assumption ($7^k = 6m + 1$): $f(k+1) = 7(6m + 1) - 1$ $f(k+1) = 42m + 7 - 1$ $f(k+1) = 42m + 6$ $f(k+1) = 6(7m + 1)$

Since $m$ is an integer, $7m+1$ is also an integer. Therefore, $f(k+1)$ is a multiple of 6. So, if $P(k)$ is true, then $P(k+1)$ is true.

Step 4: Conclusion Since $P(1)$ is true, and we have shown that $P(k) \implies P(k+1)$, by the principle of mathematical induction, the statement is true for all integers $n \ge 1$.