Proof by Induction

• Proof by Induction is a formal method of mathematical proof used to establish that a given statement $P(n)$ is true for all natural numbers $n \ge n_0$, where $n_0$ is a specified initial integer, often 0 or 1. It is particularly effective for statements involving sequences, series, divisibility, and properties of recursively defined structures.

• The underlying principle is often compared to the domino effect: if you can show that the first domino falls, and that if any domino falls, the next one will also fall, then all dominoes in the line will eventually fall. This analogy clearly illustrates the two main logical steps required for the proof.

• This method is essential for proving properties that hold for an infinite set of integers, where direct verification for each integer is impossible. It provides a rigorous way to generalize from a specific case to an entire domain of numbers.

• The statement $P(n)$ typically involves an integer variable $n$, and the goal is to demonstrate its truth for all $n$ in a specified range, usually positive integers or non-negative integers.

• The validity of proof by induction stems from the Well-Ordering Principle for natural numbers, which states that every non-empty set of natural numbers has a least element. If a statement $P(n)$ were false for some $n \ge n_0$, then the set of integers for which $P(n)$ is false would have a least element, say $m$.

• If $m = n_0$, this contradicts the Basic Step where $P(n_0)$ is proven true. If $m > n_0$, then $P(m)$ is false, but $P(m-1)$ must be true (since $m$ is the least integer for which $P(n)$ is false).

• However, the Inductive Step proves that if $P(k)$ is true, then $P(k+1)$ must also be true. Therefore, if $P(m-1)$ is true, then $P((m-1)+1) = P(m)$ must also be true, which contradicts our assumption that $P(m)$ is false. This logical contradiction proves that no such $m$ can exist, and thus $P(n)$ must be true for all $n \ge n_0$.

• This method is a form of deductive reasoning, where the truth of a general statement is inferred from the truth of a specific base case and a rule for progression. It is not an empirical method, but a rigorous logical argument.

• Step 1: The Basic Step (Base Case): This involves proving that the statement $P(n)$ is true for the initial value $n_0$. This is typically $n=1$ for statements about positive integers, or $n=0$ for non-negative integers, but can be any integer $n_0$ from which the statement is claimed to hold. Without a true base case, the inductive chain cannot begin.

• Step 2: The Assumption Step (Inductive Hypothesis): Here, one assumes that the statement $P(k)$ is true for some arbitrary integer $k \ge n_0$. This assumption is crucial as it forms the premise for proving the next case. It is not proven, but rather accepted as a temporary truth to facilitate the next step.

• Step 3: The Inductive Step: This is the core of the proof, where you must show that if $P(k)$ is true (from the assumption), then $P(k+1)$ must also be true. This step typically involves algebraic manipulation, using the assumption $P(k)$ to transform the expression for $P(k+1)$ into a form that demonstrates its truth. The goal is to derive $P(k+1)$ from $P(k)$.

• Step 4: The Conclusion Step: Finally, a formal concluding statement is made, summarizing how the basic step and the inductive step together prove the statement for all integers in the specified range. This step explicitly links the two parts of the proof, often using standard phrasing to ensure logical completeness and clarity.

Proofs for Series and Sums

• When proving formulas for sums or series, the statement $P(n)$ typically equates a summation (LHS) to a closed-form expression (RHS). In the inductive step, the sum for $n=k+1$ is usually split into the sum for $n=k$ plus the $(k+1)$-th term. The assumption for $P(k)$ is then substituted into the sum for $n=k$, allowing for algebraic simplification to match the RHS for $n=k+1$.

• For example, proving $\sum_{r=1}^{n} r = \frac{n(n+1)}{2}$ involves showing $P(1)$ is true, assuming $P(k)$ is true, and then showing $\sum_{r=1}^{k+1} r = (\sum_{r=1}^{k} r) + (k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{(k+1)(k+2)}{2}$, which is $P(k+1)$.

Proofs for Divisibility

• For divisibility proofs, $P(n)$ states that an expression $f(n)$ is divisible by a certain integer $d$. The inductive hypothesis assumes $f(k)$ is a multiple of $d$, often written as $f(k) = dm$ for some integer $m$. The inductive step then manipulates $f(k+1)$ to show it can also be expressed as a multiple of $d$, often by isolating a term related to $f(k)$ or by showing $f(k+1) - f(k)$ is a multiple of $d$.

• A common technique is to express a term like $a^{k+1}$ as $a \cdot a^k$ and substitute the assumption $a^k = dm \pm \text{other terms}$. Alternatively, showing $f(k+1) - f(k)$ is divisible by $d$ implies that if $f(k)$ is divisible by $d$, then $f(k+1)$ must also be.

Proofs for Sequences and Recurrence Relations

• When proving properties of sequences defined by recurrence relations, $P(n)$ usually asserts that the $n$-th term $u_n$ follows a specific explicit formula. The basic step verifies the formula for the initial term(s) given by the recurrence relation.

• In the inductive step, the recurrence relation for $u_{k+1}$ is used, and the assumed explicit formula for $u_k$ is substituted into it. The resulting expression is then simplified to match the explicit formula for $u_{k+1}$. If the recurrence relation depends on more than one previous term (e.g., $u_{n+1}$ depends on $u_n$ and $u_{n-1}$), then multiple base cases (e.g., $n=1$ and $n=2$) might be required.

Proofs for Matrices

• For matrix proofs, $P(n)$ typically states a formula for the $n$-th power of a matrix, $M^n$. The basic step verifies the formula for $M^1$ (which is just $M$). The inductive hypothesis assumes $M^k$ follows the given formula.

• The inductive step involves calculating $M^{k+1}$ as $M^k \cdot M$ (or $M \cdot M^k$). The assumed formula for $M^k$ is substituted, and matrix multiplication is performed. The result must then match the original formula with $n$ replaced by $k+1$. This often requires careful algebraic manipulation of the matrix elements.

• Base Case Selection: The choice of the base case $n_0$ is critical and depends on the domain of the statement. For statements about positive integers, $n_0=1$ is common. For non-negative integers, $n_0=0$ is used. For sequences defined by multiple previous terms (e.g., Fibonacci sequence), multiple base cases (e.g., $P(1)$ and $P(2)$) may be necessary to ensure the inductive step can always refer to valid previous terms.

• Strong Induction vs. Weak Induction: The standard method described (assuming $P(k)$ to prove $P(k+1)$) is called weak induction. Strong induction assumes $P(i)$ is true for all integers $i$ such that $n_0 \le i \le k$ to prove $P(k+1)$. While strong induction appears more powerful, it is logically equivalent to weak induction; any proof by strong induction can be converted to a proof by weak induction, and vice-versa.

• Algebraic Manipulation in Inductive Step: The most challenging part is often the algebraic manipulation in the inductive step. It requires careful use of the inductive hypothesis to transform the expression for $P(k+1)$ into the desired form. This often involves factoring, expanding, or rearranging terms to reveal the structure of $P(k+1)$.

• Distinction from Direct Proof: Induction is not a direct proof. A direct proof starts with premises and logically deduces the conclusion. Induction proves a statement for an infinite set by establishing a starting point and a propagation rule, rather than directly proving each instance.

• Follow the Four Steps Rigorously: Always clearly label and execute each of the four steps: Basic Step, Assumption Step, Inductive Step, and Conclusion Step. Missing or poorly executed steps can lead to loss of marks.

• State the Inductive Hypothesis Clearly: Explicitly write down 'Assume $P(k)$ is true for some integer $k \ge n_0$'. This sets up the premise for your inductive step.

• Show the Link to $P(k)$ in the Inductive Step: When manipulating $P(k+1)$, clearly indicate where you are using the assumption $P(k)$. For sums, this means substituting the assumed sum for $k$ terms. For divisibility, it means substituting $f(k) = dm$ or similar.

• Algebraic Precision is Key: The inductive step often boils down to algebraic simplification. Be meticulous with your calculations, factoring, and expansion. A single algebraic error can invalidate the entire inductive step.

• Master the Conclusion Wording: Memorize and use the standard concluding phrases. For example: "If it is true for $n=k$, then it is true for $n=k+1$. As it is true for $n=n_0$, the statement is true for all $n \in \mathbb{Z}^+$ (or $n \ge n_0$)." This ensures you correctly articulate the logical flow of the proof.

• Check the Base Case Carefully: Ensure you substitute $n_0$ correctly into both sides of the statement (if applicable) and show they are equal. An incorrect base case means the entire proof fails.

• Assuming $P(k+1)$ is true: A common mistake is to assume $P(k+1)$ is true and work backwards, rather than deriving $P(k+1)$ from $P(k)$. The goal is to show $P(k) \implies P(k+1)$, not $P(k+1) \implies P(k)$.

• Algebraic Errors: Many errors occur during the algebraic manipulation in the inductive step. These can include incorrect factoring, sign errors, or misapplying index laws, especially in divisibility or matrix proofs.

• Incorrect Base Case: Failing to prove the base case, or choosing an inappropriate base case, invalidates the entire proof. For instance, if a statement is true for $n \ge 0$, proving only for $n=1$ might be insufficient if $n=0$ is the true starting point.

• Missing the Conclusion: Even if the basic and inductive steps are perfect, a proof by induction is incomplete without a clear, formal conclusion that ties the two parts together and states the range of $n$ for which the statement is proven.

• Not Using the Inductive Hypothesis: Some students attempt to prove $P(k+1)$ directly without making use of the assumption $P(k)$. The inductive hypothesis is the bridge that connects $P(k)$ to $P(k+1)$, and its omission means the proof is not inductive.