1. 개요
mathematical induction · 數 學 的 歸 納 法자연수에 관한 명제 [math(P(n))]이 모든 자연수(또는, 어떤 자연수보다 큰 모든 자연수)에 대하여 성립함을 보이는 증명법이다.[1]
2. 설명
귀납논증이라는 이름 때문에 혼동하기 쉽지만, 엄밀히 말하면 연역논증의 일종이다. 증명 과정이 타당하다면 결론 역시 반드시 타당하기 때문에 완전귀납법이라고도 한다.증명은 두 부분으로 구성되는데, 첫 번째 부분은 최소원 [math(n=n_0)]에 대해 [math(P(n_0))]가 성립함을 보이는 부분이며, 두 번째 부분에서는 어떤 자연수 [math(k)]에 대해 [math(P(k))]가 성립한다는 가정 하에 [math(P(k+1))] 또한 성립함을 보이게 된다.
영어로는 흔히 첫 번째 부분을 basis step, 두 번째 [math(n)]에대한 임의의 상수 [math(k)]를 가정하는 부분을 assumption step, 세 번째 [math(k+1)] 또한 [math(n)]에서 성립함을 보이는 부분을 inductive step, 네 번째 결론을 도출하는 부분을 conclusion step이라 한다.
전제하는 원리는 다음과 같다.
가산무한집합 [math(X)]가 자연수 집합 [math(\mathbb{N})]의 부분집합일 때
|
이 때, [math(P(n))]이 모든 자연수에 대하여 성립함을 보이기 위해 다음 2가지만 보이면 된다.
|
수학적 귀납법과 동치이지만 뭔가 조건이 좀 더 강해보이는 강한 수학적 귀납법이라는 것도 있다. 구체적으로는 [math(P(n))]이 성립하는 것을 확인하기 위해서는 다음을 증명하면 된다. 하지만, 본질적으로 수학적 귀납법과 동일하다.
|
실제 증명에서는 원래 수학적 귀납법 못지 않게 강한 수학적 귀납법을 자주 사용한다. 많은 경우 [math(P(n+1))]을 보이기 위해 [math(P(n))]이 성립할 때 생기는 무언가보다 [math(P(1),\,P(2),\,\cdots,\,P(n))] 중 어떤 하나에서 생기는 무언가를 쓰는 게 더 적절하기 때문이다.[3] 조건이 강해 보여서 쓰기 불편해 보이겠지만 그건 큰 오해이다. 원래 수학적 귀납법의 것보다 더 잔뜩 가정해 놓고[4] 그 중에 원하는 거 아무 거나 한두 개 골라 쓰는 것인데도 패널티가 생기기는커녕 이게 원래 수학적 귀납법과 사실 상 동치이니, 오히려 더 편리한 녀석이라고 할 수도 있다.
많은 경우 1번 스텝보다 2번 스텝을 보이는 게 훨씬 더 어렵다. 사실 1번 스텝은 많은 경우 '자명하다' 한 마디로 끝내도 좋을 정도이다. 예를 들어 [math(n)]이 어떤 벡터 공간의 차원이면 이런 상황이 자주 발생한다. 즉, [math(n = 1)]일 때 다루는 대상이 엄청 단순하거나 매우 구체적이면 1번 스텝 역시 단순해진다. 하지만 물론 1번 스텝이 항상 그렇게 쉬운 단계이진 않다. 오히려 경우에 따라선 1번 스텝이 훨씬 더 어려워지고 2번 스텝은 단순해지는 경우도 종종 발생한다.[5]
정수론에서 가장 중요한 증명법 중에 하나이다. 단점은, 범위가 자연수(혹은 확장한다고 해도 정수)에서만 성립한다는 것이다.[6] 초한귀납법이 있긴 하지만 생각보다 그리 자주 쓰이지는 않는다. 그럼에도 수학적 귀납법은 정수론 뿐만 아니라 많은 분야에서 쏠쏠히 잘 쓰이는데[7], 많은 수학적 대상들이 자연수로 된 핵심적인 파라미터(parameter)를 가지기 때문이다. 다항식의 차수라든가 유한 차원 벡터 공간의 차원[8], 그리고 수열[9]의 인덱스가 가장 대표적인 예이다. 그리고 이런 대상들이 정수론, 대수학은 물론 기하학, 해석학, 위상수학을 포함한 수학 전반에서 몹시 자주 나타나고, 이들 혹은 이들을 활용한 어떤 대상의 성질을 규명할 때 이들 자연수 파라미터가 핵심으로 작용하니, 수학적 귀납법은 유한귀납법만 있어도 어디에서든 강력한 도구로 활용된다.
사실 증명 과정에서 은연 중에 수학적 귀납법을 쓰는 경우가 많다. 예를 들어 어떤 작업을 한 다음, 뭔가 더 작은 것이 나왔고 (여기에다 이해를 돕기 위해 한 번 더 비슷한 작업을 할 수도 있지만) 그 다음에 "... 이 작업을 (그 작은 것에) 계속 반복하다 보면..."라고 쓰는 경우가 왕왕 있는데, 여기서 수학적 귀납법을 썼다고 보면 된다. 사실 이런 반복 작업을 수학적으로 형식화한 것이 바로 수학적 귀납법이다.
수학적 귀납법도 다변수함수처럼 다차원 수학적 귀납법, 다변수 수학적 귀납법을 상정해볼 수 있다.
3. 유한 귀납법
주어진 명제에 대하여,즉, [math(n=1)]의 경우 성립한다. [math(n)]이 성립하면, [math(n+1)]이 성립한다. 여기서 [math(n=1)]로 둘 때 [math(n+1=2)]에서 성립한다. 또 여기서 [math(n=2)]에서 성립하므로 [math(n+1=3)]에서도 성립한다. 이하 무한 반복. 이렇게 하면 무한대까지 쭉쭉 뻗어나가 모든 자연수에서 성립한다는 것이다.
이것을 수학적인 표현을 사용하면
|
[math((P(0)\quad\&\quad(\forall n\in N\quad P(n)
\Rightarrow P(n+1))) \Rightarrow \forall n\in N\quad P(n))]
|
3.1. 강한 수학적 귀납법
위의 귀납법을 이에 대비하여 약한 귀납법이라고도 한다. 이는 약한 귀납법과 동치임이 알려져있지만, 약한 귀납법보다 강력하다. 이 단락에서는 구분을 위해 모두 약한·강한 귀납법이라고 명시할 것이다.
자연수의 부분집합 [math(S)]가 다음 조건을 만족하면, [math(S)]는 자연수 전체의 집합 그 자체이다.
|
- [증명]
- -----
집합 [math(S)]가 강한 귀납법의 조건을 만족시킨다고 할 때, 다음의 집합을 생각하자.
[math(\displaystyle T=\{n\in\mathbb N|[0,n]\cap \mathbb N \subset S\} )]
이제 이 집합에 대해 약한 귀납법을 사용할 것이다.
먼저, [math(1\in S)]이므로, [math(1\in T)]인 것은 자명하다. [math(S)]가 강한 수학적 귀납법의 조건을 만족시킨다고 했으니, [math(1,2,\cdots,k \in S)]이면 [math(k+1\in S)]이다. 그 말은 곧, [math(k\in T)]이면 [math(k+1\in S)]이라는 말이 되고, [math(k \in T)]가
[math(1,\,2,\,\cdots,\,k \in S)]
라고 정의했으니
이다.
[math(k\in T \Rightarrow 1,\,2,\,\cdots,\,k \in S \wedge k+1\in S \Leftrightarrow k+1\in T)]
약한 귀납법에 의해 [math(T=\mathbb N)]이고, [math(n\in\mathbb T \Rightarrow 1,2,\cdots,n\in S\Rightarrow n\in S)]이니 모든 자연수는 [math(S)]의 원소가 된다.
- [강한 귀납법으로 약한 귀납법의 증명]
- -----
다음은 강한 귀납법으로 약한 귀납법을 증명한 것이다. 우선 [math(S)]가 약한 귀납법을 만족시킨다고 하자. 그러면,- [math(1\in S)]
- [math(k\in S \Rightarrow k+1\in S)]
[math(1,\,2,\,\cdots,\,k \in S \Rightarrow k \in S \Rightarrow k+1\in S)]
이므로, 강한 귀납법에 의해 [math(S=\mathbb N)]이 된다.
4. 초한 귀납법
자연수를 확장한 서수(초한서수), 기수(초한기수)에 대해서 적용하기 위해서, 수학적 귀납법을 확장한 것이다.
|
이 세 가지를 하나의 sentence로 묶을 수 있다. [math(A)]가 well-ordered class(모든 subclass에 supremum이 존재하는 class)이고, [math(P(x))]를 각각의 원소 [math(x\in A)]에 대해 참과 거짓이 명백한 명제라 하자. 다음 조건이 모든 [math(x\in A)]에 대해 성립한다면, [math(P(x))]는 모든 원소 [math(x\in A)]에 대해 참이다.
| [math(\forall y\in A (y<x\Rightarrow P(y))\Rightarrow P(x))] |
5. 매거적 귀납법
수학적 귀납법과는 또 다른 형태의 완전 귀납법. 수학적 귀납법도 내용을 보면 매거적 귀납법과 공통 분모가 있기는 하지만, 수학적 귀납법에서 증명하는 명제는 '[math(n=1)]에서 성립한다' 와 '[math(n=a)]에서 성립한다면 [math(n=a+1)]에서 성립한다'라는 단 두 가지 명제이기 때문에...문자 그대로, 특정 집합에 있는 모든 원소에서 해당 명제가 성립함을 모든 원소를 일일이 언급해 가면서 직접 증명하는 방법이다. 하지만 귀납법의 생명이 해당 명제를 일반화할 수 있다는 것, 즉 그 집단에서의 일부분의 성질만 조사하고서도 그 성질을 집단 전체의 성질로 확장할 수 있다는 점,[12] 치명적으로 이전까지의 답이 다음 답은 완전히 보증하지 않는다는 점 때문에, 아리스토텔레스는 매거적 귀납법을 '사이비 귀납법'이라고 불렀다.
6. 예시
6.1. 예시 1
|
[문제] 모든 자연수 [math(n)]에 대하여 [math(\displaystyle \sum_{k=1}^{n}(-1)^{k+1}k^{2} = \frac{(-1)^{n+1} n(n+1)}{2} \quad \cdots \, \small{(\ast)} )] 임을 수학적 귀납법을 사용하여 증명하시오. |
[math(n=1)]일 때, 식 [math((\ast))]는
[math(\displaystyle \begin{aligned} \sum_{k=1}^{1}(-1)^{k+1}k^{2}&=1 \\ \frac{(-1)^{1+1} \cdot 1(1+1)}{2}&=1 \end{aligned} )]
으로, 성립한다.
[math(n=m)]일 때,
[math(\displaystyle \begin{aligned} \sum_{k=1}^{m}(-1)^{k+1}k^{2} = \frac{(-1)^{m+1} m(m+1)}{2} \quad \cdots \,\small{(\#)} \end{aligned} )]
이 성립한다고 가정하면 [math(n=m+1)]일 때,
[math(\displaystyle \begin{aligned} \sum_{k=1}^{m+1}(-1)^{k+1}k^{2} = \frac{(-1)^{m+2} (m+1)(m+2)}{2} \end{aligned} )]
이다. 한편, 식 [math(\small{(\#)})]이 성립하기 때문에
[math(\displaystyle \begin{aligned} \sum_{k=1}^{m+1}(-1)^{k+1}k^{2} &=\frac{(-1)^{m+1} m(m+1)}{2} +(-1)^{m+2}(m+1)^{2} \\ &=-\frac{(-1)^{m+2} m(m+1)}{2} +(-1)^{m+2}(m+1)^{2} \\ &=(-1)^{m+2} \left[(m+1)^{2}-\frac{m(m+1)}{2} \right] \\ &= \frac{(-1)^{m+2}(m+1)(m+2)}{2} \end{aligned} )]
따라서 [math(k=m+1)]일 때도 식이 성립하므로 증명이 끝났다.
6.2. 예시 2
|
[문제] 모든 자연수 [math(n)]에 대하여 [math(\displaystyle 6 \biggl(\sum_{k=1}^{n} k \biggr)\biggl(\sum_{k=1}^{n} k^{2} \biggr) =5 \sum_{k=1}^{n} k^{4}+\sum_{k=1}^{n} k^{2} \quad \cdots \, \small{(\ast)} )] 임을 수학적 귀납법을 사용하여 증명하시오. |
[math(m=1)]일 때,
[math(\displaystyle \begin{aligned} 6 \biggl(\sum_{k=1}^{1} k \biggr)\biggl(\sum_{k=1}^{1} k^{2} \biggr)&=6 \\ 5 \sum_{k=1}^{1} k^{4}+\sum_{k=1}^{1} k^{2}&=6 \end{aligned} )]
으로, 성립한다.
[math(k=m)]일 때,
[math(\displaystyle 6 \biggl(\sum_{k=1}^{m} k \biggr)\biggl(\sum_{k=1}^{m} k^{2} \biggr) =5 \sum_{k=1}^{m} k^{4}+\sum_{k=1}^{m} k^{2} \quad \cdots \, \small{(\#)} )]
이 성립한다고 가장하면, [math(k=m+1)]일 때,
[math(\displaystyle 6 \biggl(\sum_{k=1}^{m+1} k \biggr)\biggl(\sum_{k=1}^{m+1} k^{2} \biggr) =5 \sum_{k=1}^{m+1} k^{4}+\sum_{k=1}^{m+1} k^{2} )]
이다.
한편,
[math(\displaystyle \begin{aligned} 6 \biggl(\sum_{k=1}^{m+1} k \biggr)\biggl(\sum_{k=1}^{m+1} k^{2} \biggr)&=6 \biggl[\sum_{k=1}^{m} k + (m+1) \biggr]\biggl[\sum_{k=1}^{m} k^{2} +(m+1)^{2} \biggr] \\ &= 6 \biggl(\sum_{k=1}^{m} k \biggr)\biggl(\sum_{k=1}^{m} k^{2} \biggr) +6(m+1)^{2}\sum_{k=1}^{m} k+6(m+1)\sum_{k=1}^{m} k^{2}+6(m+1)^{3} \end{aligned} )]
그런데, 식 [math(\small(\#))]이 성립하기 때문에
[math(\displaystyle \begin{aligned} 6 \biggl(\sum_{k=1}^{m+1} k \biggr)\biggl(\sum_{k=1}^{m+1} k^{2} \biggr)&=5 \sum_{k=1}^{m} k^{4}+\sum_{k=1}^{m} k^{2}+3{m(m+1)^3}+m(m+1)^2(2m+1)+6(m+1)^{3} \\ &=5\sum_{k=1}^{m} k^{4}+\sum_{k=1}^{m} k^{2}+5(m+1)^4+(m+1)^2 \\ &=5\sum_{k=1}^{m+1} k^{4}+\sum_{k=1}^{m+1} k^{2}\end{aligned} )]
이므로 [math(n=m+1)]일 때도 성립하므로 증명이 끝났다.
6.3. 예시 3
|
[문제] [math(n \geq 2)]인 자연수 [math(n)]에 대하여 [math(\displaystyle \biggl(1+\frac{1}{1^{3}} \biggr)\biggl(1+\frac{1}{2^{3}} \biggr)\biggl(1+\frac{1}{3^{3}} \biggr) \cdots \biggl(1+\frac{1}{n^{3}} \biggr) < 3-\frac{1}{n} \quad \cdots \, \small{(\ast)} )] 임을 수학적 귀납법을 사용하여 증명하시오. |
[math(n=2)]일 때
[math(\displaystyle \begin{aligned} \biggl(1+\frac{1}{1^{3}} \biggr)\biggl(1+\frac{1}{2^{3}} \biggr) =\frac{9}{4} > 1-\frac{1}{2} =\frac{1}{2} \end{aligned} )]
이므로 부등식이 성립한다.
[math(n=k)]일 때
[math(\displaystyle \biggl(1+\frac{1}{1^{3}} \biggr)\biggl(1+\frac{1}{2^{3}} \biggr)\biggl(1+\frac{1}{3^{3}} \biggr) \cdots \biggl(1+\frac{1}{k^{3}} \biggr) < 3-\frac{1}{k} \quad \cdots \, \small{(\#)} )]
이 성립한다고 가정하자.
한편, [math(n=k+1)]일 때
[math(\displaystyle \biggl(1+\frac{1}{1^{3}} \biggr)\biggl(1+\frac{1}{2^{3}} \biggr)\biggl(1+\frac{1}{3^{3}} \biggr) \cdots \biggl(1+\frac{1}{k^{3}} \biggr) \biggl(1+\frac{1}{(k+1)^{3}} \biggr)<3-\frac{1}{k+1} )]
이때, [math(\small (\#))]에 의하여
[math(\displaystyle \biggl(1+\frac{1}{1^{3}} \biggr)\biggl(1+\frac{1}{2^{3}} \biggr)\biggl(1+\frac{1}{3^{3}} \biggr) \cdots \biggl(1+\frac{1}{k^{3}} \biggr) \biggl(1+\frac{1}{(k+1)^{3}} \biggr)<\biggl( 3-\frac{1}{k} \biggr) \biggl(1+\frac{1}{(k+1)^{3}} \biggr) )]
다음을 계산하면
[math(\displaystyle \biggl(3-\frac{1}{k+1} \biggr)-\biggl[\biggl(3-\frac{1}{k} \biggr) \biggl(1+\frac{1}{(k+1)^{3}} \biggr) \biggr]>0 \quad \to \quad \biggl(3-\frac{1}{k} \biggr) \biggl(1+\frac{1}{(k+1)^{3}} \biggr) < 3-\frac{1}{k+1})]
이상에서 다음이 성립한다.
[math(\displaystyle \biggl(1+\frac{1}{1^{3}} \biggr)\biggl(1+\frac{1}{2^{3}} \biggr)\biggl(1+\frac{1}{3^{3}} \biggr) \cdots \biggl(1+\frac{1}{k^{3}} \biggr) \biggl(1+\frac{1}{(k+1)^{3}} \biggr)< 3-\frac{1}{k+1} )]
따라서 [math(n=k+1)]일 때도 이 부등식이 성립하므로 증명이 끝났다.
7. 기타
- 애매한 표현을 이용해서 암울한 현실을 유머적으로 표현하는데 쓰이기도 한다. 더미의 역설 참조.
8. 관련 문서
[1]
사실 자연수일 필요는 없다.
Well-ordered class의 특수한 경우가 자연수일 뿐이다. 정수여도 된다.
[2]
만약 최소원이 [math(1)]이 아닌 [math(2)] 이상의 정수 [math(a)]라면, 이 성질을 만족하는 집합 [math(X)]는 집합 [math(\mathbb{N}-\{1,\,\cdots,\,a-1\})]이 된다.
[3]
가장 대표적인 예로
차원에 대한 수학적 귀납법을 쓰면서 몫공간(quotient space)을 증명에 쓰는 경우를 들 수 있다. 이 몫공간은 보통 원래 주어진 공간의 차원보다 딱 하나 더 낮은 차원을 가지지 않기 때문이다.
[4]
그냥 가정만 하면 된다. 원래 버전에선 '이제 [math(P(n))]을 가정하자'로 되어 있던 것을 '이제 [math(P(1),\,P(2),\,\cdots,\,P(n))]을 가정하자'로 바꾸기만 하면 된다.
[5]
예를 들어 J. M. Lee, Introduction to Smooth Manifolds, 2nd Ed. (Springer, 2012)의 Theorem C.34를 보자.
[6]
미친 짓을 한다면 자연수[math(\times)]자연수(그러니까 (자연수, 자연수) 좌표계)에서도 사용할 수는 있다.
선택공리에 의하여 [math(\mathbb{N}^{n}\sim\mathbb{N})]이기 때문. 그러니까 잘하면 유리수까지는 가능하다는 이야기. 근데 실수부터는 안 된다. 자세한 건
연속체 가설의 설명 참조.
[7]
오히려 초한귀납법을 이용한 케이스가 유한 귀납법보다 훨씬 더 적다.
[8]
무한 차원도 있지만 많은 경우 유한 차원인 벡터 공간들만 가지고 논다. 사실 유한 차원 벡터 공간들을 다루는 것과 무한 차원 벡터 공간들을 다루는 것 간에는 엄청난 차이가 있다.
[9]
'수의 열' 뿐만 아니라 수를 넘어 임의의 무언가(예를 들어, 함수, 집합)로 구성된 sequence 전체.
[10]
굳이 [math(n)]을 1로만 둘 필요는 없다. 필요하다면 [math(n=2,\,n=100,\,n=3000)] 등 원하는 [math(n)]에 대해서 참인지 따져봐도 되고, 충분히 큰 모든 [math(n)]에 대해 어떤 성질이 항상 성립하는가 하는 걸 알아보고 싶다면 (주로 어떤 수열의 수렴성을 보일 때 나타난다) '정확히 얼마인지는 알 바 아니고 여튼 유한한 [math(n)] 어딘가'에서 참이라는 것만 보여도 된다. 물론 [math(n)]이 [math(1~100)]일 때에 대해 관심이 있는데 기본 경우를 [math(n=101)]같이 알아보고자 하는 범위를 포함하지 않도록 잡으면 당연히 안 된다.
[11]
그러니까, 수학적 귀납법을 풀 때는 해당하는 명제가 [math(\boldsymbol{n=k})]에서 성립하는지 안 하는지를 밝힐 필요가 없다. 더 정확하게 말하자면, [math(\boldsymbol{n=k})]일 때 성립하는지 밝히는 것은 해당 명제를 증명하는 것과 같다. 수학적 귀납법을 처음 배우는 고등학생들이 이 부분을 정말 헷갈려하는데, 이것만 이해하면 수학적 귀납법은 꽤 쉬워질 것이다.
[12]
일단 수학적 귀납법에서는 그 명제가 참이라는 것을 직접 밝혀야 하는 원소는 맨 처음의 원소 하나밖에 없다.