Proof by Induction

Prove that for all positive integers \(n\), \(3^{2n+2} + 8n -9 \) is divisible by 8.

Solution

First define \(f(n) = 3^{2n+2} + 8n -9 \).

Step 1: Now consider the base case. Since the question says for all positive integers, the base case must be \(f(1)\). You can substitute \(n=1\) into the formula to get

\[ \begin{align} f(1) = 3^{2+2} + 8 - 9 & = 3^4 - 1 \\ & = 81 - 1 \\ & = 80. \end{align} \]

80 is clearly divisible by 10, hence the condition is true for the base case.

Step 2: Next, state the inductive hypothesis. This assumption is that \(f(k) = 3^{2k + 2} + 8k - 9 \) is divisible by 8.

Step 3: Now, consider \(f(k+1)\). The formula will be:

\[ \begin{align} f(k+1) & = 3^{2(k+1)+2} + 8(k + 1) - 9 \\ & = 3^{2k + 4} + 8k + 8 -9 \\ & = 3^{2k+4} + 8k -9 + 8. \end{align} \]

It may seem weird to write it like this, without simplifying the \(8-9\) to become \(-1\). There is a good reason to do this: you want to keep the formula as similar to the formula of \(f(k)\) as you can since you need to transform it into this somehow.

To do this transformation, notice that the first term in \(f(k+1) \) is the same as the first term in \(f(k)\) but multiplied by \(3^2 = 9\). Hence, you can split this up into two separate parts.

\[ \begin{align} f(k+1) & = 9 \cdot 3^{2k+2} + 8k -9 + 8 \\ & = 3^{2k+2} + 8 \cdot 3^{2k+2} + 8k -9 + 8 \\ & = (3^{2k+2} + 8k -9) + 8 \cdot 3^{2k+2} + 8 \\ & = f(k) + 8 \cdot 3^{2k+2} + 8. \end{align} \]

The first term in this is divisible by 8 because of the assumption, and the second and third terms are multiples of 8, thus they are divisible by 8 too. Since this is the sum of different terms that are all divisible by 8, \(f(k+1)\) must also be divisible by 8 too, assuming the inductive hypothesis is true. Hence, you have proven the inductive step.

Step 4: Finally, remember to write the conclusion. This should sound something like:

If it is true that \( f(k) \) is divisible by 8, then it will also be true that \(f(k+1) \) is divisible by 8. Since it is true that \(f(1)\) is divisible by 8, it is true that \(f(n)\) is divisible by 8 for all positive integers \(n\).

Prove that for any non-negative integer \(n\),

\[ |\sin{(nx)}| \leq n \sin{x}, \]

for \( x \in (0, \pi) \).

Solution

Step 1: The base case is clear, since substituting in \(n=1\) makes the inequality \( |\sin{x}| \leq{\sin{x}}\), which is true for \( x \in (0, \pi) \).

Step 2: For the induction hypothesis, assume that \[ | \sin{(mx)} | \leq m \sin{x}. \]

Step 3: You must now prove that \( |\sin{((m+1)x)}| \leq (m+1) \sin{x}. \) First, you can expand the bracket of the left hand side:

\[ |\sin{((m+1)x)}| = |\sin{(mx + x)}| \]

Now, you can use the trigonometric sum of angles formula for the sine function.

\[ |\sin{((m+1)x)}| = |\sin{(mx)} \cos{(m)} + \cos{(mx)} \sin{(m)}|. \]

From here, you can use thetriangle inequality for absolute values:\( | a + b| \leq |a| + |b| \).

\[ |\sin{((m+1)x)}| \leq |\sin{(mx)} \cos{(x)}| + |\cos{(mx)} \sin{(x)}|. \]

Remember that \( \cos{(mx)} \) and \( \cos{(x)} \) are less than one. Hence, you can create a new upper bound by estimating the cosine functions as 1:

\[ \begin{align} |\sin{((m+1)x)}| &\leq |\sin{(mx)} \cos{(x)}| + |\cos{(mx)} \sin{(x)}| \\ &\leq |\sin{(mx)}| + |\sin{(x)}|. \end{align} \]

From here, notice that there is \( |\sin{(mx)}| \) on the left-hand side. This is where you can use the inductive hypothesis. You know \( |\sin{(mx)}| \leq m \sin{x}\), so you can create another upper bound:

\[ \begin{align} |\sin{((m+1)x)}| &\leq |\sin{(mx)}| + |\sin{(x)}| \\ &\leq m \sin{(x)} + |\sin{(x)}|. \end{align} \]

Finally, as was stated in the base case, \( |\sin{(x)}| \leq \sin{(x)} \).S,

\[ |\sin{((m+1)x)}| \leq m \sin{(x)} + \sin{(x)} = (m+1)\sin{(x)}, \]

as required.

Step 4: Finally, state the conclusion. We have proved that the inequality holds for \( n = m+1 \) if it holds for \( n = m.\) Since it holds for \(n=1\), by induction it will hold for all positive integers.

Prove that any integer \(n \geq 2\) can be written as a product of primes.

Solution

Step 1: First, prove the base case, which in this case requires \(n=2\). Since \(2 \) is already a prime number, it is already written as a product of primes, and hence the base case it true.

Step 2: Next, state the inductive hypothesis. You will assume that for any \( 2 \leq n \leq k\), \(n\) can be written as a product of primes.

Step 3: Finally, you must use the assumption to prove that \(n=k+1 \) can be written as a product of primes. There are two cases:

• \(k+1\) is a prime number, in which case it is clearly already written as the product of primes.
• \(k+1\) is not a prime number and there must be a composite number.

如果\ (k + 1 \)不是质数,这意味着它μst be divisible by a number other than itself or 1. This means there exists \(a_1\) and \(a_2\), with \(2 \le a_1\) and \(a_2 \le k\), such that \(k+1 = a_1 a_2. \) By the inductive hypothesis, \(a_1\) and \(a_2\) must have a prime decomposition, since \(2 \le a_1\) and \(a_2 \le k\). This means there exist prime numbers \( p_1,\dots ,p_i\) and \(q_1,\dots ,q_j\) such that

\[ \begin{align} a_1 & = p_1\dots p_i \\ a_2 & = q_1 \dots q_j. \end{align} \]

Finally, since\(k+1 = a_1 a_2, \) you have:

\[ k+1 = p_1\dots p_i q_1\dots q_j \]

which is a product of primes. Hence, this is a prime decomposition for \(k+1\).

Step 4: \(k+1\) will have a prime decomposition if all numbers \(n\), \(2 \leq n \leq k \) also have a prime decomposition. Since 2 has a prime decomposition, therefore by induction every positive integer greater than or equal to 2 must have a prime decomposition.

Prove that for any positive integer \(n\),

\[ 1^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}. \]

Solution

Step 1: First, consider the base case, when \(n=1\). The left-hand side is clearly just 1, while the right-hand side becomes

\[ \frac{1 \cdot 2 \cdot 3}{6} = \frac{6}{6} = 1. \]

Hence, the base case is correct.

Step 2: Next, write the induction hypothesis. This is that

\[ 1^2 + \dots + m^2 = \frac{m(m+1)(2m+1)}{6}. \]

Step 3: Finally, prove the inductive step. The left-hand side, for \(n=m+1\), will be:

\[ 1^2 +\dots + m^2 + (m+1)^2 = (1^2 +\dots + m^2) + (m+1)^2. \]

The first \(n\) terms in this are in the inductive hypothesis. Thus, you can replace these with the right-hand side from the inductive hypothesis:

\[ \begin{align} 1^2 +\dots + m^2 + (m+1)^2 & = \frac{m(m+1)(2m+1)}{6} + (m+1)^2 \\ & = \frac{m(m+1)(2m+1) + 6(m+1)^2}{6} \\ & = \frac{(m+1)\left[m(2m+1) + 6(m+1)\right]}{6}. \end{align}\]

Next, expand the bit inside of the square brackets, so you will have a quadratic. Then you can solve the quadratic normally:

\[ \begin{align} 1^2 +\dots + m^2 + (m+1)^2 & = \frac{(m+1)\left[2m^2+1m + 6m+6\right]}{6} \\ & = \frac{(m+1)[2m^2 + 7m + 6}{6} \\ & = \frac{(m+1)(m+2)(2m+3)}{6} \\ & = \frac{(m+1)((m+1)+1)(2(m+1)+1)}{6}, \end{align}\]

as required. Thus, you have proven the inductive step.

Step 4: Finally, write the conclusion. If the sum of squares formula is true for any positive integer \(m\), then it will be true for \(m+1\). Since it is true for \(n=1\), it is true for all positive integers.

Prove Binet's Formula using induction.

Solution

Step 1: First, prove the induction base. This will be for \(F_0\) and \(F_1\). For \(F_0\):

\[\frac{\phi^0 - \hat{\phi}^0}{\sqrt{5}} = \frac{1-1}{5} = 0, \]

which is the value of \( F_0\) as expected.

For \(F_1\):

\[ \begin{align} \frac{\phi - \hat{\phi}}{\sqrt{5}} & = \frac{\frac{1+\sqrt{5}}{2} \frac{1-\sqrt{5}}{2}}{\sqrt{5}} \\ & = \frac{1}{\sqrt{5}}\cdot \frac{1-1 +\sqrt{5} + \sqrt{5}}{2} \\ & = 1, \end{align} \]

which is the expected answer. Thus, the induction base is proven.

Step 2: Next, state the induction hypothesis. In this case, strong induction must be used. The hypothesis is that for any \( 0 \leq i \leq k+1, \)

\[ F_i = \frac{\phi^i + \hat{\phi}^i}{\sqrt{5}}. \]

Step 3: Now you must prove the induction step, which is that

\[F_{k+2} = \frac{\phi^{k+2} + \hat{\phi}^{k+2}}{\sqrt{5}}.\]

Start with the right-hand side and try and simplify it until you reach the left-hand side. First, start by splitting thepowerof \(k+2\) into 2 separate terms, one with the power of \(k\) and the other with the power of \(2\).

\[ \frac{\phi^{k+2} + \hat{\phi}^{k+2}}{\sqrt{5}} = \frac{\phi^2 \phi^k + \hat{\phi}^2 \hat{\phi}^k}{\sqrt{5}} \]

Now, you can use the result that \( \phi^2 = 1 + \phi\) and \( \hat{\phi}^2 = 1 + \hat{\phi} \).

\[ \begin{align} \frac{\phi^{k+2} + \hat{\phi}^{k+2}}{\sqrt{5}} & = \frac{(1+\phi) \phi^{k} + (1+\hat{\phi}) \hat{\phi}^{k}}{\sqrt{5}} \\ & = \frac{\phi^{k} + \hat{\phi}^{k} + \phi^{k+1} + \hat{\phi}^{k+1}}{\sqrt{5}} \\ & = \frac{\phi^{k} + \hat{\phi}^{k}}{\sqrt{5}} + \frac{\phi^{k+1} + \hat{\phi}^{k+1}}{\sqrt{5}} \\ & = F_k + F_{k+1} \\ & = F_{k+2}. \end{align} \]

And thus, the induction step has been proved. The step that gets the answer to \( F_k + F_{k+1} \) requires the use of the induction hypothesis to get there.

Step 4: Finally, the conclusion: If Binet's Formula holds for all non-negative integers up to \(k+1\), then the formula will hold for \(k+2\). Since the formula holds for \(F_0\) and \(F_1\), the formula will hold for all non-negative integers.