⊢

Mathematical Induction

★★★☆☆High School

📖Definition

Mathematical induction proves statements about natural numbers. It consists of base case (n=1) and inductive step (n=k → n=k+1).

P(1) ∧ (∀ k (P(k) → P(k+1))) ⇒ ∀ n P(n)

Principle of mathematical induction

예제 1

Prove 1 + 2 + ... + n = n(n+1)/2 by induction.

Discovered by: Pascal, Fermat (17th century)

The principle is inherent in natural number definition, explicitly used from 17th century.

Series formulas, inequality proofs

Recursive algorithm analysis

Grammar property proofs

#귀납법#증명#induction#proof