The Basics of Writing an Induction Proof (support file not provided - please refer to the descriptive text)

Description

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.