Problem 17 - Algebra and Trigonometry

Question

Show that \(8^{n}-3^{n}\) is divisible by 5 for all natural numbers \(n.\)

Step-by-Step Solution

Answer

By induction, \(8^n - 3^n\) is divisible by 5 for all natural numbers \(n\).

Step 1: Base Case

We start by verifying the theorem for the smallest natural number, which is \( n = 1 \). We calculate \( 8^1 - 3^1 \) and check if it is divisible by 5. \[8^1 - 3^1 = 8 - 3 = 5\]Since 5 is divisible by 5, the base case holds.

Step 2: Inductive Hypothesis

Assume that the statement is true for some arbitrary natural number \( k \), i.e., assume that \( 8^k - 3^k \) is divisible by 5. This means:\[8^k - 3^k = 5m\]for some integer \( m \).

Step 3: Inductive Step

Now, we need to show that the statement holds for \( k+1 \) given it is true for \( k \). Consider:\[8^{k+1} - 3^{k+1} = 8 \cdot 8^k - 3 \cdot 3^k\]We rewrite this expression:\[8 \cdot 8^k - 3 \cdot 3^k = 8^k \cdot 8 - 3^k \cdot 3\]Notice that:\[8 \cdot 8^k - 3 \cdot 3^k = (8 \cdot 8^k - 8 \cdot 3^k) + (8 \cdot 3^k - 3 \cdot 3^k)\]The first part simplifies to:\[8(8^k - 3^k) \quad ext{which is divisible by 5 by Inductive Hypothesis}\]The second part is:\[3^k(8 - 3) = 3^k \cdot 5\]which is clearly divisible by 5.

Step 4: Conclusion

Since both terms \( 8(8^k - 3^k) \) and \( 3^k \cdot 5 \) are divisible by 5, their sum \( 8^{k+1} - 3^{k+1} \) is also divisible by 5.Thus, by the principle of mathematical induction, \( 8^n - 3^n \) is divisible by 5 for all natural numbers \( n \).

Key Concepts

Divisibility

Divisibility is a fundamental concept in number theory. It describes when one integer can be evenly divided by another. If a number \(a\) is divisible by another number \(b\), it means that dividing \(a\) by \(b\) leaves no remainder. In mathematical terms, \(a\) can be expressed as \(b \times k\) for some integer \(k\).
For example, if we say 10 is divisible by 5, we mean \(10 = 5 \times 2\), with no remainder after division.
When applied to our task of proving that \(8^n - 3^n\) is divisible by 5, we mean that for each integer \(n\), the outcome of \(8^n - 3^n\) divided by 5 should not leave a remainder. This forms the basis of our proof.

Inductive Hypothesis

In mathematical induction, the inductive hypothesis is a crucial step. It assumes that a statement is true for some arbitrary case, often denoted by \(k\). This assumption helps bridge the statement from one case to the next.
To apply it, we start by assuming: \(8^k - 3^k = 5m\) for some integer \(m\). This assumption allows us to explore if the statement holds for the subsequent number, \(k+1\).
Without the inductive hypothesis, transitioning from one example to an endless chain of truths would be impossible. It effectively builds a ladder, stepping from one truth to the next.

Base Case

The base case is the starting point in a proof by induction. It verifies the initial instance of a statement. Without a valid base case, the foundation of the induction process fails.
In our exercise, the base case is for \(n = 1\). We checked \(8^1 - 3^1 = 5\), easily observing that 5 is divisible by itself.
Checking this ensures that our inductive process begins correctly. It is akin to verifying the first rung of a ladder is secure before climbing. A successful base case is therefore crucial for the entire proof.

Inductive Step

The inductive step is where the true power of mathematical induction shines. It involves proving that if a statement holds for a certain number \(k\), it also holds for \(k+1\).
In the given problem, after establishing the base case and hypothesis for \(k\), we calculate \(8^{k+1} - 3^{k+1}\). By rewriting and manipulating it, we show this expression is divisible by 5 as well.
This step involves logical reasoning:

• Utilizing the inductive hypothesis \((8^k - 3^k)\) and its divisibility by 5.
• Breaking down the expression for \(k+1\) into parts that are each individually divisible by 5.

Successfully completing this step confirms that the statement can be extended indefinitely, validating the proof.