数学归纳法原理

Introduction: Compressing Infinitely Many Verifications into Two Steps

The Induction Axiom

In the induction axiom, which two conditions guarantee $A=\mathbb{N}$?

The Induction Recipe

What are the two steps of mathematical induction?

Example: Sum of the First n Odd Numbers

It can be proved by induction that $\sum_{j=1}^{n}j=\dfrac{n(n+1)}{2}$. Use this to compute $\sum_{j=1}^{100}j$; enter an integer.

General Starting Point

Example: n Factorial Greater Than 2 to the n

When the proposition $P(n)$ holds only for $n\ge a$, how should induction be adjusted?

Verify the induction basis of $n!>2^n$: compute $4!$; enter an integer.

Strong Induction

What is the induction hypothesis of strong induction?

Example: Existence of Binary Representation

In the strong induction proof of binary representation, when $k+1$ is even, the binary representation of $k+1$ is obtained by left-shifting the representation of which number?

Counterexample: All Horses Same Color

In the false proof of "all horses same color", at which $k$ does the induction step fail?

In your own words, explain: where does the induction proof of "all horses same color" go wrong? At which $k$ does the induction step fail, and why?

What are the two steps of induction? How does the induction hypothesis of strong induction differ from ordinary induction?

Comprehensive Check

Lesson Summary