Standard Proofs by Induction

• Well-Ordering Principle: The validity of mathematical induction is rooted in the well-ordering principle, which states that every non-empty set of positive integers contains a least element. This principle ensures that if a statement were false for some integer, there would be a first integer for which it is false, which induction then contradicts.

• Logical Implication: The inductive step establishes a conditional truth: 'If $P(k)$ is true, then $P(k+1)$ is true.' This is a logical implication, not an assertion that $P(k)$ is true. The base case then provides the initial truth ($P(n_0)$ is true) that 'activates' this chain of implications, proving $P(n_0+1)$, then $P(n_0+2)$, and so on.

• Foundation for Recursion: Induction is closely related to recursive definitions and algorithms. Just as a recursive function defines a base case and a rule for subsequent cases, induction proves properties of such functions or sequences by mirroring this structure.

• Step 1: Basic Step ($n=n_0$): Substitute the base case value (often $n=1$) into both sides of the summation formula. Calculate the Left-Hand Side (LHS) and Right-Hand Side (RHS) independently to show they are equal, thus proving the statement for the initial value.

• Step 2: Assumption Step ($n=k$): Clearly state the inductive hypothesis: assume the given formula is true for an arbitrary positive integer $k$. This means writing out the entire summation formula with $n$ replaced by $k$. For example, assume $\sum_{r=1}^{k} f(r) = G(k)$ is true.

• Step 3: Inductive Step ($n=k+1$): The core of the proof involves showing that if the statement is true for $k$, it must also be true for $k+1$. Start with the LHS of the statement for $n=k+1$, which is $\sum_{r=1}^{k+1} f(r)$.

• Manipulation for Series: Rewrite the LHS for $n=k+1$ by separating the last term: $\sum_{r=1}^{k+1} f(r) = \left(\sum_{r=1}^{k} f(r)\right) + f(k+1)$. Substitute the assumption from Step 2 into the summation part, replacing $\sum_{r=1}^{k} f(r)$ with $G(k)$.

• Algebraic Simplification: Perform algebraic manipulation on the resulting expression $G(k) + f(k+1)$ to transform it into the RHS of the original formula with $n$ replaced by $k+1$, i.e., $G(k+1)$. This often involves factoring and expanding polynomials.

• Step 4: Conclusion Step: Conclude the proof by explicitly stating that since the statement is true for the base case and the inductive step holds, it is true for all integers $n \ge n_0$. Use the standard wording: "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}^+"$.

Key Strategy for Series: The primary technique is to split the sum for $n=k+1$ into the sum for $n=k$ plus the $(k+1)$-th term, then apply the inductive hypothesis and simplify algebraically to match the expected form for $n=k+1$.

• Step 1: Basic Step ($n=n_0$): Substitute the base case value (e.g., $n=1$ or $n=0$) into the expression $f(n)$. Show that the resulting value is indeed divisible by the specified integer. For example, if proving divisibility by 3, show $f(n_0)$ is a multiple of 3.

• Step 2: Assumption Step ($n=k$): Assume that the statement is true for an arbitrary positive integer $k$. This means assuming $f(k)$ is divisible by the integer, which can be written as $f(k) = Xm$, where $X$ is the divisor and $m$ is some integer. It is often helpful to rearrange this assumption to isolate a term, such as $4^k = 1+3m$ if proving $4^n-1$ is divisible by 3.

• Step 3: Inductive Step ($n=k+1$): Consider the expression $f(k+1)$. The goal is to show that $f(k+1)$ can also be expressed as a multiple of $X$. Substitute $n=k+1$ into the original expression.

• Manipulation for Divisibility: Use algebraic manipulation and the assumption from Step 2 to rewrite $f(k+1)$. This often involves using index laws (e.g., $a^{k+1} = a \cdot a^k$) to introduce a term that can be replaced by the assumption $Xm$. The aim is to factor out $X$ from the entire expression for $f(k+1)$.

• Alternative Method (Difference): Sometimes, it's easier to show that the difference $f(k+1) - f(k)$ is divisible by $X$. If $f(k+1) - f(k) = Xp$ (where $p$ is an integer) and $f(k) = Xm$ (by assumption), then $f(k+1) = f(k) + Xp = Xm + Xp = X(m+p)$, which proves $f(k+1)$ is also divisible by $X$. This method is not always applicable but can simplify certain proofs.

• Step 4: Conclusion Step: As with series proofs, clearly state the conclusion using the standard wording, confirming the statement's truth for all relevant integers based on the base case and inductive step.

Key Strategy for Divisibility: Express $f(k)$ as $Xm$ (where $X$ is the divisor). Then, manipulate $f(k+1)$ to isolate a term that can be replaced by the assumption, aiming to factor out $X$ from the entire expression.

• Step 1: Basic Step ($n=n_0$): Verify the explicit formula for the sequence at the base case (e.g., $n=1$). This involves calculating the first term using the recursive definition and comparing it to the value obtained by substituting $n=1$ into the proposed explicit formula. They must match.

• Step 2: Assumption Step ($n=k$): Assume the explicit formula is true for an arbitrary integer $k$. This means assuming $u_k = G(k)$, where $G(k)$ is the proposed explicit formula for the $k$-th term. This assumption is applied to the explicit formula, not the recursive one.

• Step 3: Inductive Step ($n=k+1$): The goal is to show that the explicit formula holds for $n=k+1$. Start by using the given recursive definition to express $u_{k+1}$ in terms of $u_k$ (or previous terms). For example, if $u_{n+1} = A u_n + B$, then $u_{k+1} = A u_k + B$.

• Substitution and Simplification: Substitute the assumption $u_k = G(k)$ into the recursive expression for $u_{k+1}$. Then, algebraically simplify the resulting expression. The aim is to transform it into $G(k+1)$, which is the explicit formula with $n$ replaced by $k+1$.

• Multiple Base Cases: If the recursive definition depends on more than one preceding term (e.g., $u_{n+2} = u_{n+1} + u_n$), then the basic step must be verified for multiple initial values (e.g., $n=1$ and $n=2$) to ensure the chain of induction is properly initiated.

• Step 4: Conclusion Step: Conclude the proof using the standard wording, confirming the explicit formula's validity for all integers $n \ge n_0$ based on the established base case(s) and the inductive step.

Key Strategy for Sequences: Use the recursive definition to relate $u_{k+1}$ to $u_k$. Then, substitute the inductive hypothesis for $u_k$ and algebraically simplify to match the explicit formula for $u_{k+1}$.

• Step 1: Basic Step ($n=n_0$): Verify the matrix power formula for the base case (usually $n=1$). Substitute $n=1$ into the proposed formula for $M^n$ and show that it equals the original matrix $M$. This confirms the formula holds for the initial power.

• Step 2: Assumption Step ($n=k$): Assume the matrix power formula is true for an arbitrary positive integer $k$. This means assuming $M^k = F(k)$, where $F(k)$ is the proposed matrix formula with $n$ replaced by $k$. Write out the full matrix equation for $M^k$.

• Step 3: Inductive Step ($n=k+1$): The goal is to show that the formula holds for $n=k+1$. Start by expressing $M^{k+1}$ using matrix properties: $M^{k+1} = M^k \cdot M^1$. This is crucial as it allows the use of the inductive hypothesis.

• Matrix Multiplication: Substitute the assumed form of $M^k$ (from Step 2) and the original matrix $M$ (which is $M^1$) into the expression $M^k \cdot M^1$. Perform the matrix multiplication carefully, ensuring all entries are correctly calculated.

• Simplification and Verification: Algebraically simplify the entries of the resulting product matrix. The final matrix should match the proposed formula for $M^n$ with $n$ replaced by $k+1$, i.e., $F(k+1)$. This confirms the inductive step.

• Step 4: Conclusion Step: Conclude the proof using the standard wording, stating that because the base case is true and the inductive step holds, the matrix power formula is true for all integers $n \ge n_0$.

Key Strategy for Matrices: Express $M^{k+1}$ as $M^k \cdot M$. Substitute the inductive hypothesis for $M^k$ and perform matrix multiplication. Simplify the resulting matrix to match the formula for $M^{k+1}$.

• Master the Four Steps: Always explicitly state and clearly label each of the four steps: Basic Step, Assumption Step, Inductive Step, and Conclusion Step. Missing or poorly articulated steps can lead to loss of marks.

• Show All Working: Especially in the inductive step, demonstrate every algebraic manipulation or substitution clearly. Do not skip steps, as examiners need to follow your logical progression from the assumption to the conclusion for $n=k+1$.

• Use the Assumption: A common mistake is failing to explicitly use the inductive assumption ($P(k)$ is true) within the inductive step. The proof is invalid if the assumption is not directly applied to transform the $n=k+1$ case.

• Exact Conclusion Wording: Memorize and use the precise concluding statement: "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}^+"$. Adjust $n_0$ (e.g., $n=0$) and the set of integers ($\mathbb{Z}^+$ or $n \ge 0$) as appropriate for the problem.

• Check the Base Case Carefully: Ensure the base case is correctly identified and verified. If the statement is for $n \ge 0$, the base case is $n=0$. If it's for $n \ge 2$, the base case is $n=2$. A faulty base case invalidates the entire proof.

• Algebraic Precision: The inductive step often boils down to careful algebraic manipulation. Double-check factorization, expansion, and simplification, as small errors here can prevent you from reaching the desired $n=k+1$ form.

• Work Backwards (Mentally): In the inductive step, it can be helpful to know what the target expression for $n=k+1$ should look like. This can guide your algebraic manipulations, but always present the proof logically from $P(k)$ to $P(k+1)$.

• Identify the Type of Proof: Before starting, determine if it's a series, divisibility, sequence, or matrix proof, as each type has specific manipulation strategies within the inductive step.