Mathematical Induction

Understand the principle of mathematical induction

  • Theory
  • Examples
    (a) Prove, by mathematical induction, that for all positive integers n, \(1 \times 2 + 3 \times 4 + 5 \times 6 + \cdots + (2n - 1)(2n) = \frac{1}{3}n(n + 1)(4n - 1)\).


    (b) Hence, according to the formula \(1 + 2 + 3 + \cdots + n = \frac{1}{2}n(n + 1)\), deduce the formula for evaluating \({2^2} + {4^2} + {6^2} + \cdots + {(2n)^2}\).
  • Solutions
    (a) Let P(n) be ‘\(1 \times 2 + 3 \times 4 + 5 \times 6 + \cdots + (2n - 1)(2n) = \frac{1}{3}n(n + 1)(4n - 1)\)’.
    When \(n = 1\), L.H.S.\( = 1 \times 2 = 2\)

    R.H.S.\( = \frac{1}{3} \times 1 \times 2 \times 3 = 2\)

    ∴P(1) is true.

    Assume that P(k) is true, where k is a positive integer.

    i.e. \(1 \times 2 + 3 \times 4 + 5 \times 6 + \cdots + (2k - 1)(2k) = \frac{1}{3}k(k + 1)(4k - 1)\)

    then \(\begin{array}{l}1 \times 2 + 3 \times 4 + 5 \times 6 + \cdots + (2k - 1)(2k) + [2(k + 1) - 1][2(k + 1)]\\ = \frac{1}{3}k(k + 1)(4k - 1) + 2(k + 1)(2k + 1)\\ = \frac{1}{3}(k + 1)[k(4k - 1) + 6(2k + 1)]\\ = \frac{1}{3}(k + 1)(4{k^2} + 11k + 6)\\ = \frac{1}{3}(k + 1)(k + 2)(4k + 3)\\ = \frac{1}{3}(k + 1)[(k + 1) + 1][4(k + 1) - 1]\end{array}\)

    ∴ \(P(k + 1)\) is true.

    According to mathematical induction, P(n) is true for all positive integers n.



    (b)

    \(\begin{array}{1}{2^2} + {4^2} + {6^2} + \cdots + {(2n)^2} = (1 + 1) \times 2 + (1 + 3) \times 4 + (1 + 5) \times 6 + \cdots + [1 + (2n - 1)](2n)\\ = 2 + 1 \times 2 + 4 + 3 \times 4 + 6 + 5 \times 6 + \cdots + 2n + (2n - 1)(2n)\\ = [1 \times 2 + 3 \times 4 + 5 \times 6 + \cdots + (2n - 1)(2n)] + (2 + 4 + 6 + \cdots + 2n)\\ = \frac{1}{3}n(n + 1)(4n - 1) + 2(1 + 2 + 3 + \cdots + n)\\ = \frac{1}{3}n(n + 1)(4n - 1) + 2[\frac{1}{2}n(n + 1)]\\ = \frac{1}{3}n(n + 1)[(4n - 1) + 3]\\ = \frac{1}{3}n(n + 1)(4n + 2)\\ = \underline{\underline {\frac{2}{3}n(n + 1)(2n + 1)}} \end{array}\)