Mathematical Induction Principle

Discrete Algebra

Binomial Theorem

Evaluation of Sums of the Form
1k + 2k + ... + nk

Model Examples
Example 1
Example 2
Example 3
Example 4
Example 5
Example 6

Mathematical Induction Principle:
Example 1

Key Topics Remaining: Examples 2, 3, 4, 5, 6,

Problem. Prove that 2n > n for all positive integers n.

Proof. Let Pn be the proofable statement:

Pn : 2n > n.

Induction basis: Since 21 = 2 > 1, the statement P1 is certainly true.
Induction hypothesis: Assume that the proofable inequality holds true for some integer n > 1.
Induction step: We have to prove that inequality
2n > n
implies inequality
2n+1 > n + 1.

Really,

2n+1 = 2·2n > 2·n = n + n ≥ n + 1.

Therefore, the statement Pn is true for any integers n ≥ 1.