The Basics of Writing an Induction Proof (support file not provided - please refer to the descriptive text)Mathematics 2U (HSC)•23-02-260
Induction Proof is a 3-step method:
1. Prove the Base Case (Multiple may be needed situationally).
2. Prove the Inductive Step. In other words: Assume that the N case is true, to prove that the N+1 case is true.
3. By the Principle of Mathematical Induction, this equation (or relevant information) is true for N [where N is in some subset of numbers].
Example Proof: Prove that 1 + 2 + 3 + ... + n = 1/2 * n (n + 1), for all positive integers n.
1. Prove the Base Case (n = 1)
LHS = 1
RHS = 1/2 * 1 * (1 + 1) = 1/2 * 1 * 2 = 1 = LHS
Therefore the Base Case has been proved.
2. Prove the Inductive Step
Assume that 1 + 2 + 3 + ... + k = 1/2 * k (k + 1), where n = k and k is a positive integer ...........................( 1 )
To prove that 1 + 2 + 3 + ... + k + (k + 1) = 1/2 * (k + 1) (k + 2) ...........................( 2 )
LHS of ( 2 ) = 1/2 * k (k + 1) + (k + 1)
= 1/2 * [k (k + 1) + 2 (k + 1)]
= 1/2 * (k + 1) (k + 2) = RHS of (2)
3. Writing the essay (* for must write this statement)
Because we have proved the Base Case n = 1,
And we have proved that n = k + 1 is true IF n = k is true,
Therefore it must be true for n = 1 + 1 = 2, n = 2 + 1 = 3, n = 3 + 1 = 4, and so on.
*Therefore by the Principle of Mathematical Induction, the statement is true for all positive integers n.