Question

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

Short answer

The proof by induction verifies that the statement \(6 \mid (n^{3} - n)\) holds for all integers \(n \geq 0\).

Step-by-step solution

Base Case

For the base case, we need to show that the statement is true for \(n = 0\). Substituting \(n = 0\) in \(n^{3} - n\), we get \(0^{3} - 0 = 0\). Since 0 is divisible by 6, we have established the base case.

Inductive Hypothesis

For the inductive hypothesis, we assume that the statement is true for \(n = k\), where \(k \geq 0\). This means that \(6 \mid (k^{3} - k)\), or equivalently, \(k^{3} - k = 6m\), for some integer \(m\).

Inductive Step

To complete the proof, we must show that the statement also holds for \(n = k + 1\). We calculate \((k + 1)^{3} - (k + 1) = k^{3} + 3k^{2} + 3k + 1 - k - 1\). Utilizing the inductive hypothesis, \(k^{3} - k = 6m\), it evolves into \(6m + 3k^{2} + 3k\). As \(3k(k+1)\) is divisible by 6 for all integers \(k\), \((k + 1)^{3} - (k + 1)\) is divisible by 6.

Key concepts

Mathematical Induction

Mathematical induction is a powerful proof technique used in mathematics to establish the truth of an infinite number of cases. It's akin to falling dominoes; if you can prove the first domino falls and that each domino will cause the next to fall, you can conclude that all dominoes will fall.

Induction consists of two main parts: the base case and the inductive step. Starting with the base case, we verify that a statement holds for an initial value, usually the smallest value from where induction is to be applied. After establishing this, we assume that the statement holds for a certain case, known as the inductive hypothesis, and then we show it's also true for the next case. The beauty of induction lies in its ability to simplify complex problems by breaking them down into more manageable steps.

Divisibility

The concept of divisibility is fundamental to many areas of mathematics, particularly in number theory. When we say that one integer is divisible by another, we mean that when you divide them, there's no remainder left over. In formal terms, an integer 'a' is divisible by another integer 'b' if there exists an integer 'c' such that a = bc.

For instance, we can say that 15 is divisible by 5 because 15 can be expressed as 5 multiplied by 3. Divisibility plays a crucial role in the types of problems that can be tackled using mathematical induction, such as proving properties of sequences or the characteristics of numbers themselves.

Inductive Step

The inductive step is where the actual work of an inductive proof happens. After assuming our statement to be true for some arbitrary value 'k' in the inductive hypothesis, the inductive step must show that the statement is also true for 'k+1'.

This involves algebraic manipulation and substitution from the inductive hypothesis to reach a form that clearly indicates our statement holds for the next logical entry in our sequence. It's the heart of the proof by induction method; success in this part ensures the domino effect of truth, ensuring every subsequent case follows the rule we're trying to prove. Without a valid inductive step, the entire proof could collapse.

Base Case

Starting any inductive proof requires that we first establish the base case. This is our proof's foundation, ensuring that the property we are trying to prove holds at the starting point. The base case is often very simple to verify and sets the stage for applying the inductive hypothesis and step.

In the context of the given exercise, proving that '6' divides 'n^3-n' for all integers 'n' greater or equal to zero, the base case we need to investigate is when 'n' is equal to zero. As the solution explains, at 'n = 0', the equation simplifies to 0, which is divisible by every number, thereby confirming the base case. Without establishing the base case, we cannot confidently move on to the inductive step, where the true inductive work happens.