Problem 7 - A Gentle Introduction to the Art of Mathematics

Question

Give inductive proofs of the following $$ \forall n \in \mathbb{N}, 4 \mid\left(13^{n}+4 n-1\right) $$

Step-by-Step Solution

Answer

Since the base case is true and the inductive step has been proven, the statement holds for all natural numbers.

Step 1: Base Case

Check the base case where n = 0. Substitute n = 0 into the expression to verify whether it is divisible by 4. \[ 13^0 + 4 \times 0 - 1 = 1 - 1 = 0 \] Since 0 is divisible by 4, the base case is true.

Step 2: Inductive Hypothesis

Assume the statement is true for some arbitrary natural number k, i.e., \[ 4 \bigg| \big(13^k + 4k - 1\big) \] This means there exists some integer m such that,\[ 13^k + 4k - 1 = 4m \]

Step 3: Inductive Step

Prove that the statement is true for k + 1 based on the inductive hypothesis. Consider \[ 13^{k+1} + 4(k+1) - 1 \]Rewrite using the properties of exponents and combine like terms: \[ 13^{k+1} + 4k + 4 - 1 = 13 \times 13^k + 4k + 3 \]Using the inductive hypothesis, substitute \( 13^k = 4m - 4k + 1 \):\[ 13 \times (4m - 4k + 1) + 4k + 3 \ = 52m - 52k + 13 + 4k + 3 \ = 52m - 48k + 16 \]Since both terms are clearly divisible by 4, we can conclude \[ 13^{k+1} + 4(k+1) - 1 = 4(13m - 12k + 4) \]Thus, the proof holds for k + 1.

Step 4: Conclusion

By mathematical induction, since the base case holds true and the inductive step has been proven, the given statement is true for all natural numbers n. Hence, \( \forall n \in \mathbb{N}, 4 | (13^n + 4n - 1) \).

Key Concepts

Base Case

In mathematical induction, we start with the base case. This is where we verify that the given statement is true for the smallest possible value of the natural number n.
For our example, the base case checks when n=0:
Substitute n=0 into the expression \(13^{0} + 4 \times 0 - 1 = 1 - 1 = 0\).
Since 0 is divisible by 4, the base case is satisfied.
This step is crucial as it establishes the initial truth of our statement before we move on to larger values of n.

Inductive Hypothesis

The inductive hypothesis involves assuming that the given statement is true for some arbitrary natural number k. This is not a proof yet but rather a stepping stone.
For our example, we assume the statement \(4 \bigg| \big(13^k + 4k - 1\big)\) is true for some integer k.
This assumption means that there exists an integer m such that \(13^k + 4k - 1 = 4m\).
The inductive hypothesis allows us to use this assumed truth to try and prove the statement for the next integer, k+1.
This logical step sets us up for the final part of the proof, showing continuity.

Inductive Step

Here, we need to prove that if the statement holds for some integer k, then it must also hold for k+1. This step solidifies our hypothesis and extends the truth to the next case.
Using our example, we need to prove that \(13^{k+1} + 4(k+1) - 1\) is divisible by 4.
First, rewrite the expression: \(13^{k+1} + 4k + 4 - 1 = 13 \times 13^k + 4k + 3\).
Next, use the inductive hypothesis where \(13^k = 4m - 4k + 1\): \(13 \times (4m - 4k + 1) + 4k + 3 = 52m - 52k + 13 + 4k + 3 = 52m - 48k + 16\).
Since all the terms in the final expression are divisible by 4, we confirm that the initial statement holds for k+1.

Mathematical Induction

Mathematical induction is a powerful proof technique used to prove statements about natural numbers. It consists of two main parts:

• Base Case: Prove that the statement holds for the initial value, usually n=0 or n=1.
• Inductive Step: Show that if the statement holds for an arbitrary natural number n=k, it must also hold for n=k+1.

By completing these steps, we can conclude the statement is true for all natural numbers.
For our example, after succeeding in the base case and inductive step, we conclude \( \forall n \in \mathbb{N}, 4 \mid \left(13^{n}+4n-1\right)\). This means the original statement is true for all natural numbers n.
Mathematical induction bridges the gap between proving a statement for a single case and proving it for all cases.