Mathematical Induction 편집하기

'''Mathematical Induction''' is a proof technique used in mathematics to establish the validity of a statement for all natural numbers. It is particularly useful for proving properties of sequences, inequalities, and recurrence relations.
==Principle of Mathematical Induction==
Mathematical induction consists of two main steps:
#'''Base Case:''' Prove that the statement holds for the smallest natural number (usually n = 1 or n = 0).
#'''Inductive Step:''' Assume the statement holds for some arbitrary natural number k (inductive hypothesis) and prove it for k + 1.
If both steps are satisfied, the statement holds for all natural numbers.
==Example Proofs==
===Sum of First n Natural Numbers===
To prove:

'''1 + 2 + 3 + ... + n = n(n + 1) / 2'''
#'''Base Case (n = 1)'''
#*1 = 1(1 + 1) / 2 = 1 (True).
#'''Inductive Step'''
#*Assume for some k:
#**1 + 2 + ... + k = k(k + 1) / 2
#*Prove for k + 1:
#**(1 + 2 + ... + k) + (k + 1) = k(k + 1) / 2 + (k + 1)
#**= (k + 1)(k / 2 + 1) = (k + 1)(k + 2) / 2 (True).
Thus, by mathematical induction, the formula holds for all n.
===Inequality Proof===
To prove:

'''2ⁿ ≥ n + 1''' for all n ≥ 1
#'''Base Case (n = 1):'''
#*2¹ = 2 ≥ 1 + 1 (True).
#'''Inductive Step:'''
#*Assume for some k:
#**2^k ≥ k + 1
#*Prove for k + 1:
#**2^(k+1) = 2 × 2^k ≥ 2(k + 1) (by induction assumption)
#**Since 2(k + 1) ≥ k + 2 for all k ≥ 1, the statement holds.
Thus, 2ⁿ ≥ n + 1 for all n ≥ 1.
==Strong Induction==
A variation of mathematical induction where the inductive step assumes the statement holds for multiple previous cases (not just k but all values up to k).

Example: Fibonacci sequence:

'''F(n) = F(n-1) + F(n-2) for n ≥ 2'''
#'''Base Case:''' F(0) = 0, F(1) = 1
#'''Inductive Hypothesis:''' Assume F(k) and F(k-1) hold.
#'''Inductive Step:''' Prove F(k+1) = F(k) + F(k-1).
==Applications==
*'''Proving formulas and sequences'''
*'''Verifying properties of algorithms'''
*'''Establishing correctness in recurrence relations'''
==See Also==
*[[Recurrence Relation]]
*[[Big O Notation]]
*[[Algorithm Complexity]]
*[[Proof by Contradiction]]
*[[Combinatorial Proof]]

*
[[분류:Algorithm]]