수학적 귀납법: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
문서 훼손 되돌림 |
편집 요약 없음 |
||
15번째 줄:
[[귀류법]]으로 증명한다. 먼저 <math>S\not=\mathbb{N}</math> 이라고 가정하자. 그러면 <math>S</math> 는 <math>\mathbb{N}</math> 의 진부분집합이므로, <math>\mathbb{N}-S\not=\emptyset</math> 이다. 따라서 [[자연수의 정렬성]]에 의해 <math>\mathbb{N}-S</math>의 최소원 <math>m</math>이 존재한다. 이때 <math>1\in S</math>이므로 <math>m>1</math>이다. 따라서 <math>m-1\in S</math>이므로, 두 번째 조건에 의해 <math>m\in S</math>이다. 이는 <math>m\not\in S</math>라는 것에 모순이 된다. 따라서 원하는 결론을 얻는다.
또한, 페아노 공리계에 의해 자명하게 여겨지기도 한다. 임의의 집합 <math>A</math>에 대하여, <math>1\in A</math>이고 <math>n\in A</math>일때, <math>n+1\in A</math>이면 <math>A\in \mathbb{N}</math>라는 공리이다.
== 예 ==
밑에서 서술될 가장 작은 <math>n</math>개의 홀수들의 합이 <math>n^2</math>이 된다는 사실을 증명한다.
일단 <math>1</math>이 명제를 성립시킴을 보인다. 가장 작은 <math>1</math>개의 홀수의 합은 <math>1</math>이고, <math>1^2</math>은 <math>1</math> 이므로 <math>1</math>은 명제를 만족한다.
임의의 수 <math>k</math>가 명제에 대해 성립한다 가정하면, <math>\overbrace{1+3+5+\cdots+(2k-3)+(2k-1)}^{k} = k^2</math>이다. 이제 이 등식이 성립한다는 전제 하에 <math>k+1</math>에 대해 성립함을 보인다. 양변에 <math>(2k+1)</math>을 더하면 <math>\overbrace{1+3+5+\cdots+(2k-1)+(2k+1)}^{k+1} = k^2 + 2k + 1</math>이다. 우변을 [[인수분해]] 하면 <math>(k+1)^2</math>이 되는데, 이는 <math>(k+1)</math>의 제곱이므로 <math>k+1</math>에 대해 성립한다.
그러므로 명제 가장 작은 <math>n</math>개의 홀수들의 합이 <math>n^2</math>가 모든 자연수 <math>n</math>에 대해 성립함을 증명하였다.
또한, 가장 작은 <math>n</math>개의 자연수의 합이 <math>\frac{n(n+1)}{2}</math>임을 증명하는 것도 쉽다.
<math>n=1</math>일때, 가장 작은 <math>n</math>개의 자연수의 합은 <math>1</math>이고, <math>\frac{1(1+1)}{2} = 1</math>이므로 등식이 성립한다.
k가 명제에 대해 성립한다 가정하면, <math>\overbrace{1+2+3+\cdots+(k-1)+(k)}^{k} = \frac{k(k+1)}{2}</math>이다. 이 가정 하에 <math>k+1</math>이 성립함을 보이려면 양변에 <math>k+1</math>을 더한다.
그러면 <math>\overbrace{1+2+3+\cdots+(k-1)+(k)+(k+1)}^{k+1} = \frac{k(k+1)}{2} + (k+1)</math>이다. 여기서 <math>\frac{k(k+1)}{2} + (k+1) = \frac{(k+1)(k+2)}{2}</math>임을 증명함을 된다. (우변이 식 <math>\frac{k(k+1)}{2}</math>에 대하여 <math>k</math>에 <math>k+1</math>을 대입시켰음을 주목하라.) 좌변을 [[통분]]하고 [[전개]]한다. <math>\frac{k(k+1)}{2} + \frac{2(k+1)}{2} = \frac{k(k+1)+2(k+1)}{2} = \frac{(k^2 +k)+(2k+2)}{2} = \frac{k^2 +3k+2}{2}</math>이다. 이를 인수분해하면 <math>\frac{k^2 +3k+2}{2} = \frac{(k+1)(k+2)}{2}</math> 이다. 즉 <math>k</math>가 성립할때 <math>k+1</math>이 성립한다. (또는, 반대로 <math>\frac{(k+1)(k+2)}{2}</math>을 전개하여 같음을 보일 수도 있다.)
그러므로 명제 가장 작은 <math>n</math>개의 자연수의 합이 <math>\frac{n(n+1)}{2}</math>가 모든 자연수 <math>n</math>에 대해 성립함을 증명하였다.
== 확장 ==
| |||