수학적 귀납법을 사용한 증명 방법 ¶
전제: 자연수 n에 관한
명제,proposition p(n)이 있다.
1. n=1일때 성립함을 보인다. (show)
2. n=k일때 성립한다고 가정한다. (assume)
3. n=k+1일때 성립함을 보인다. (show)
Principle of Mathematical Induction ¶
Let
Sn be a
진술,statement about the positive integer
n.
Suppose that
- S1 is true.
- Sk+1 is true whenever Sk is true.
Then
Sn is true for all positive integers
n.
(Stewart Calculus 7e, p.98)
Proof by induction ¶
수학적
귀납,induction법을 쓴
증명,proof법
- 성질(property)이 입력 크기(input size) 1인 경우에 성립함(holds)을 증명 (base_case)
- 성질이 입력 크기 에서 까지 성립한다고 가정
- 성질이 입력 크기 에서 성립함을 보임(show)
그러면, 성질은 모든 입력 크기
에 대해 성립한다.
(김황남)
Uses ¶
수학적귀납법의 사용처, 사용 예
(Stewart 9e p734)
한계, 약점, 단점 ¶
자연수에 대한 명제에만 적용 가능?
- 이 표현을 어디서 봤더라? 아무튼, 그니까... 이산적인 steps로 환원가능하고(reducible), 그 steps 사이에 명확한 점화관계(
점화식,recurrence_relation) 가 있는, 이런 경우에만 사용가능. 이 생각이 맞는지? chk
other resources ¶
이것의 자연스러운 일반화: well-founded_induction - 작성중
Related: