HSC Extension 1 and 2 Mathematics/3-Unit/HSC/Induction

From Wikibooks, open books for an open world
Jump to: navigation, search

Induction is a form of proof useful for proving equations involving non-closed expressions (i.e., expressions with n terms; sequences).

Explanation[edit]

Induction involves first proving that the equation is true for n = 1, then proving true for n = k + 1 (assuming for the purpose of the proof that the equation holds true for n = k). Since it is true for n = k and true for n = k+1, and also true for n = 1, it is true for n = 2. It follows that it is true for all positive integers n.

Examples[edit]

Proving the formula for the sum of a series[edit]

Q: Prove by mathematical induction that for all integers n \ge 1,

1^3 + 2^3 + 3^3 + 4^3 + \cdots + n^3 =  (1+2+3+....n)^2

A:

  1. When n = 1, 1^3 = 1 = \tfrac{1}{4} (1)^2((1)+1)^2 = \tfrac{1}{4}(4) = 1, so it is true for n = 1
  2. Suppose that the statement is true for k, k \in \mathbb{N}. That is, suppose that 1^3 + 2^3 + 3^3 + 4^3 + \cdots + k^3 = \tfrac{1}{4} k^2 (k+1)^2. This is sometimes called the induction hypothesis.
  3. Then prove the statement for n = k+1 (that is, prove that 1^3 + 2^3 + 3^3 + \cdots + (k+1)^3 = \tfrac{1}{4} (k+1)^2(k+2)^2:
    
\begin{align}
  \mbox{LHS} & = 1^3 + 2^3 + 3^3 + 4+3 + \cdots + k^3 + (k+1)^3 \\
             & = \tfrac{1}{4} k^2 (k+1)^2 + (k+1)^3                & \mbox{ (by the induction hypothesis)} \\
             & = \tfrac{1}{4}(k+1)^2(k^2 + 4(k+1)) \\
             & = \tfrac{1}{4}(k+1)^2(k^2 + 4k + 4) \\
             & = \tfrac{1}{4}(k+1)^2(k+2)^2 \\
             & = \mbox{RHS}
\end{align}
  4. It follows from parts 1 and 2 by mathematical induction that the statement is true for all positive integers n.