Skip to main content
Engineering LibreTexts

3.4: Mathematical Induction

  • Page ID
    9676
  • The structure of the natural numbers—0, 1, 2, 3, and on to infinity—makes possible a powerful proof technique known as induction or mathematical induction. Although the idea behind induction is simple, students often struggle with it. Take your time and study this material thoroughly! You will have opportunity to practice in the labs after we discuss induction in the lectures.

    Let be a one-place predicate whose domain of discourse includes the natural numbers. Suppose that we can prove that P(0) is true. Suppose that we can also prove the statements P(0) → P(1), P(1) → P(2), P(2) → P(3), and so on. The principle of mathematical induction is the ob- servation that we can then conclude that P(n) is true for all natural numbers n. This should be clear. It’s like a line of dominos, lined up and ready to fall, one after the next.3 Since P(0) and P(0) → P(1) are true, we can apply the rule of modus ponens to conclude that P(1) is true. Then, since P(1) and P(1) → P(2) are true, we can conclude by modus ponens that P(2) is true. From P(2) and P(2) → P(3), we conclude that P(3) is true. For any given in the set N, we can continue this chain of deduction for steps to prove that P(n) is true. When applying induction, we don’t actually prove each of the implications P(0) →P(1), P(1) → P(2), and so on, individually. That would require an infinite amount of work. The whole point of induction is to avoid any infinitely long process. Instead, we prove ∀(P(k) → P(+ 1)) (where the domain of discourse for the predicate is N. The statement ∀(P(k) → P(+ 1)) summarizes all the infinitely many implications in a single statement. Stated formally, the principle of mathematical induction says that if we can prove the statement P(0) ∧ (∀(P(k) → P(+ 1)), then we can deduce that∀n P(n) (again, with N as the domain of discourse).

    屏幕快照 2019-07-02 14.11.34.png

    Khan Academy offers a video with a clear explanation of mathematical induction: www.khanacademy.org/math/algebra-home/ alg-series-and-induction/alg-induction/v/proof-by-induction.
    I highly recommend that you watch it to also hear this information from another perspective.