Question

Prove the following statements with either induction, strong induction or proof by smallest counterexample. Prove that \(9 \mid\left(4^{3 n}+8\right)\) for every integer \(n \geq 0\).

Short answer

By mathematical induction, it has been proven that \(9 \mid\left(4^{3 n}+8\right)\) for every integer \(n \geq 0\).

Step-by-step solution

Base Case

First, check the statement for the base case (n=0), which results in \(4^{3*0} + 8 = 1 + 8 = 9\). Since 9 divides 9, the statement holds for the base case.

Inductive Hypothesis

Assume the statement is true for an arbitrary non-negative integer, say \(n=k\). That is, assume that \(9 \mid (4^{3k} + 8)\). This means there exists an integer, say \(m\), such that \(4^{3k} + 8 = 9m\).

Inductive Step

Now, prove the statement true for \(n=k+1\). Simplify \(4^{3*(k+1)} + 8 = 4^{3k} * 4^3 + 8\). According to the inductive hypothesis, insert \(9m\) for \(4^{3k} + 8\). This leads to \(9m*64 + 8 = 576m + 8 = 9(64m) + 8\). The result is divisible by 9, hence the statement is true for \(n=k+1\) whenever it's true for \(n=k\).

Conclusion

Therefore, by the principle of mathematical induction, the statement \(9 \mid\left(4^{3 n}+8\right)\) for every integer \(n \geq 0\) has been proven true.