# 수학적 귀납법 분야: 대수 학교급: 고등 정식 URL: https://pi.devxdev.xyz/wiki/math/%EC%88%98%ED%95%99%EC%A0%81_%EA%B7%80%EB%82%A9%EB%B2%95 --- ## 정의 **수학적 귀납법**(mathematical induction)은 자연수 $n$에 대한 명제 $p(n)$이 모든 자연수 $n$에 대하여 성립함을 증명하는 방법이다. 다음 두 단계를 모두 보이면 된다. 1. **기초 단계**: $n=1$일 때 $p(1)$이 성립한다. 2. **귀납 단계**: $n=k$일 때 $p(k)$가 성립한다고 가정하면($k$는 임의의 자연수), $n=k+1$일 때도 $p(k+1)$이 성립한다. 이 두 조건이 모두 확인되면, 모든 자연수 $n$에 대하여 $p(n)$이 성립한다고 결론지을 수 있다. ## 직관 수학적 귀납법은 **도미노**를 넘어뜨리는 원리와 같다. 첫 번째 도미노($n=1$)가 넘어지고, "어떤 도미노가 넘어지면 바로 다음 도미노도 넘어진다"는 규칙(귀납 단계)만 확인되면, 도미노가 끝없이 이어져 있어도 결국 모든 도미노가 넘어진다는 것을 알 수 있다. 무한히 많은 자연수 하나하나를 직접 대입해 확인할 수는 없지만, "처음 것이 되고, 하나가 되면 다음 것도 된다"는 두 가지만 보이면 전체가 성립함을 보장할 수 있다는 것이 핵심이다. ## 예시 **예시 1** — 등식 $1+2+\cdots+n = \dfrac{n(n+1)}{2}$가 모든 자연수 $n$에서 성립함을 증명하자. - 기초 단계: $n=1$일 때 좌변 $=1$, 우변 $=\dfrac{1\cdot2}{2}=1$이므로 성립한다. - 귀납 단계: $n=k$일 때 $1+2+\cdots+k = \dfrac{k(k+1)}{2}$가 성립한다고 가정하자. 이 식의 양변에 $k+1$을 더하면 $$1+2+\cdots+k+(k+1) = \frac{k(k+1)}{2}+(k+1) = \frac{(k+1)(k+2)}{2}$$ 이는 $n=k+1$일 때의 식과 같으므로 $n=k+1$일 때도 성립한다. 따라서 모든 자연수 $n$에 대하여 위 등식이 성립한다. **예시 2** — $3^n-1$이 2의 배수임을 증명하자. - 기초 단계: $n=1$일 때 $3^1-1=2$이고, 2는 2의 배수이다. - 귀납 단계: $n=k$일 때 $3^k-1$이 2의 배수라고 가정하면 $3^k-1=2m$($m$은 정수)로 쓸 수 있다. 그러면 $$3^{k+1}-1 = 3\cdot 3^k - 1 = 3(2m+1)-1 = 6m+2 = 2(3m+1)$$ 이므로 $3^{k+1}-1$도 2의 배수이다. 따라서 모든 자연수 $n$에 대하여 $3^n-1$은 2의 배수이다. ## ⚠️ 흔한 실수 - **잘못된 생각**: "$n=k$일 때 성립한다고 가정한다"는 부분을 이미 증명된 사실을 사용하는 것으로 착각한다. → **왜 틀렸는가**: 귀납 단계는 "$p(k)$가 참이라면 $p(k+1)$도 참이다"라는 **조건문 자체**를 증명하는 것이다. $p(k)$ 자체가 참이라고 미리 확정 짓는 것이 아니라, 가정 하에 논리적 연결고리를 만드는 과정임을 이해해야 한다. - **잘못된 생각**: 귀납 단계만 보이고 기초 단계 확인을 생략하거나, 반대로 기초 단계만 확인하고 안심한다. → **왜 틀렸는가**: 귀납 단계만으로는 "성립하는 도미노가 있다면 다음 것도 넘어진다"는 것만 보일 뿐, 애초에 첫 도미노가 넘어지는지는 알 수 없다. 두 단계는 반드시 모두 필요하다. - **잘못된 생각**: $n=k+1$일 때의 식을 귀납적 가정($p(k)$)을 전혀 사용하지 않고 처음부터 다시 계산해서 증명하려 한다. → **왜 틀렸는가**: 이는 수학적 귀납법이 아니라 그냥 각 경우를 따로 증명하는 것과 같아, $n=k+1$과 $p(k)$ 사이의 연결을 보이지 못한다. 반드시 가정한 $p(k)$의 식을 변형해 $p(k+1)$을 이끌어내야 한다. ## 확인 문제 1. 수학적 귀납법으로 어떤 명제를 증명할 때 반드시 확인해야 하는 두 단계는 무엇인가? 2. $2+4+6+\cdots+2n = n(n+1)$임을 수학적 귀납법으로 증명하시오. 3. $n=k$일 때 성립을 가정하고 $n=k+1$일 때를 유도했지만 기초 단계($n=1$)를 확인하지 않았다면, 이 증명은 완성된 것인가? 정답 보기: 1. 기초 단계($n=1$일 때 성립)와 귀납 단계($n=k$일 때 성립을 가정하면 $n=k+1$일 때도 성립함을 보이는 것). 2. 기초 단계: $n=1$일 때 좌변 $=2$, 우변 $=1\cdot2=2$로 성립. 귀납 단계: $n=k$일 때 $2+4+\cdots+2k=k(k+1)$을 가정하면, 양변에 $2(k+1)$을 더해 $2+4+\cdots+2k+2(k+1) = k(k+1)+2(k+1) = (k+1)(k+2)$가 되어 $n=k+1$일 때도 성립한다. 3. 아니다. 귀납 단계만으로는 첫 자연수에서 명제가 실제로 성립하는지 보장할 수 없으므로, 기초 단계를 반드시 확인해야 증명이 완성된다. ## 관련 개념 - 명제 — 참·거짓을 판별할 수 있는 문장으로, 귀납법으로 증명하는 대상인 $p(n)$ 자체가 명제이다. - 수열 — 자연수 $n$에 대해 정의된 수열의 일반항이나 합의 공식을 귀납법으로 증명하는 경우가 많다. - 등차수열, 등비수열 — 이 수열들의 합 공식을 귀납법으로 검증할 수 있다. - 이항정리 — 전개식의 계수 공식을 증명할 때 수학적 귀납법이 활용되기도 한다. - 부등식 — 자연수에 대한 부등식(예: $2^n>n$)을 증명하는 데 수학적 귀납법이 널리 쓰인다. --- 관련 개념: - 명제 (/wiki/math/%EB%AA%85%EC%A0%9C) - 수열 (/wiki/math/%EC%88%98%EC%97%B4) - 등차수열 (/wiki/math/%EB%93%B1%EC%B0%A8%EC%88%98%EC%97%B4) - 등비수열 (/wiki/math/%EB%93%B1%EB%B9%84%EC%88%98%EC%97%B4) - 이항정리 (/wiki/math/%EC%9D%B4%ED%95%AD%EC%A0%95%EB%A6%AC) - 부등식 (/wiki/math/%EB%B6%80%EB%93%B1%EC%8B%9D)