귀납법의 원리
Q. n≥n0인 모든 값에서 어떤 함수 F(n)이 항상 참이라는 것을 증명하라.
- 풀이 방법
1. F(n0)이 참이라는 것을 보인다.
2. F(n0)이 임의의 n에 대해 F(n)이 성립한다고 가정한다.
3. 이러한 가정에서 F(n + 1)이 성립한다는 것을 보인다면 n ≥ n0에 대해 F(n)이 성립한다는 것이 증명된다.
이를 '귀납정 정리'라고 한다.
- 예제 풀이
1. n = 0일 때: 0(0+1) / 2 = 0 → Base Step
2. 주어진 n에 대해: n(n+1) / 2 = 참이라고 가정
3. 위의 가정을 이용해 다음이 성립함을 보임 → Induction Step
= (n+1)(n+2) / 2
'자료구조&알고리즘' 카테고리의 다른 글
| 알고리즘 분석 (0) | 2022.02.11 |
|---|---|
| 자료구조와 알고리즘 (0) | 2022.02.11 |
| 추상 데이터형 (0) | 2022.02.10 |
| 자료구조를 위한 수학 (0) | 2022.02.09 |
| 자료구조와 알고리즘의 이해 (0) | 2022.02.09 |