수학적 귀납법(數學的歸納法, 영어: mathematical induction)은 모든 자연수가 어떤 주어진 성질을 만족시킨다는 명제를 증명하는 방법의 하나이다. 가장 작은 자연수(문맥에 따라 0일 수도 1일 수도 있다)가 그 성질을 만족시킴을 증명한 뒤, 만약 어떤 자연수가 만족시키면 바로 다음 자연수 역시 만족시킴을 증명하기만 하면, 모든 자연수에 대한 증명이 끝난다. 이는 임의의 정초 관계를 갖춘 집합 위의 초한 귀납법으로 확장할 수 있다. 수학적 귀납법은 이름과는 달리 귀납적 논증이 아닌 연역적 논증에 속한다. 수학적 귀납법은 자연수의 페아노 공리계의 공리이며, 메타논리학적 추론 규칙이기도 하다.
자연수의 (
2차 논리) 이론인
페아노 공리계에서는 다음과 같은
공리가 등장한다. 임의의 1항 술어
<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(-)}"><semantics><annotation encoding="application/x-tex">{\displaystyle P(-)}</annotation></semantics></math>
가 다음 두 조건을 만족시킨다고 하자.
- <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(0)}"><semantics><annotation encoding="application/x-tex">{\displaystyle P(0)}</annotation></semantics></math>
이 성립한다.
- 임의의 <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\in \mathbb {N} }"><semantics><annotation encoding="application/x-tex">{\displaystyle n\in \mathbb {N} }</annotation></semantics></math>
에 대하여, 만약 <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(n)}"><semantics><annotation encoding="application/x-tex">{\displaystyle P(n)}</annotation></semantics></math>
이 성립한다면, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(n+1)}"><semantics><annotation encoding="application/x-tex">{\displaystyle P(n+1)}</annotation></semantics></math>
역시 성립한다.
그렇다면, 임의의
<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\in \mathbb {N} }"><semantics><annotation encoding="application/x-tex">{\displaystyle n\in \mathbb {N} }</annotation></semantics></math>
에 대하여,
<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(n)}"><semantics><annotation encoding="application/x-tex">{\displaystyle P(n)}</annotation></semantics></math>
이 성립한다. 이 공리를
수학적 귀납법이라고 한다. 이를 기호로 표기하면 다음과 같다.
- <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \forall P(-)((P(0)\land \forall n(P(n)\implies P(n+1)))\implies \forall nP(n))}"><semantics><annotation encoding="application/x-tex">{\displaystyle \forall P(-)((P(0)\land \forall n(P(n)\implies P(n+1)))\implies \forall nP(n))}</annotation></semantics></math>

수학적 귀납법을 구체적으로 서술하면 다음과 같다. 임의의 자연수 부분 집합
<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S\subseteq \mathbb {N} }"><semantics><annotation encoding="application/x-tex">{\displaystyle S\subseteq \mathbb {N} }</annotation></semantics></math>
이 다음 두 조건을 만족시킨다고 하자.
- <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0\in S}"><semantics><annotation encoding="application/x-tex">{\displaystyle 0\in S}</annotation></semantics></math>

- 임의의 <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\in \mathbb {N} }"><semantics><annotation encoding="application/x-tex">{\displaystyle n\in \mathbb {N} }</annotation></semantics></math>
에 대하여, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\in S}"><semantics><annotation encoding="application/x-tex">{\displaystyle n\in S}</annotation></semantics></math>
라면, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n+1\in S}"><semantics><annotation encoding="application/x-tex">{\displaystyle n+1\in S}</annotation></semantics></math>
그렇다면,
<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S=\mathbb {N} }"><semantics><annotation encoding="application/x-tex">{\displaystyle S=\mathbb {N} }</annotation></semantics></math>
이다. (즉, 임의의
<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\in \mathbb {N} }"><semantics><annotation encoding="application/x-tex">{\displaystyle n\in \mathbb {N} }</annotation></semantics></math>
에 대하여,
<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\in S}"><semantics><annotation encoding="application/x-tex">{\displaystyle n\in S}</annotation></semantics></math>
이다.) 이를 기호로 표기하면 다음과 같다.
- <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \forall S\subseteq \mathbb {N} (0\in S\supseteq S+1\implies S=\mathbb {N} )}"><semantics><annotation encoding="application/x-tex">{\displaystyle \forall S\subseteq \mathbb {N} (0\in S\supseteq S+1\implies S=\mathbb {N} )}</annotation></semantics></math>

수학적 귀납법의 여러 가지 변형 또는 일반화가 존재하며, 이들은 수학적 귀납법을 사용하여 증명된다.
시작점[편집]
정수 <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m\in \mathbb {Z} }"><semantics><annotation encoding="application/x-tex">{\displaystyle m\in \mathbb {Z} }</annotation></semantics></math>
가 주어졌을 때, 임의의 정수 부분 집합
<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S\subseteq \mathbb {Z} }"><semantics><annotation encoding="application/x-tex">{\displaystyle S\subseteq \mathbb {Z} }</annotation></semantics></math>
가 다음 두 조건을 만족시킨다고 하자.
- <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m\in S}"><semantics><annotation encoding="application/x-tex">{\displaystyle m\in S}</annotation></semantics></math>

- 임의의 <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\in \mathbb {Z} }"><semantics><annotation encoding="application/x-tex">{\displaystyle n\in \mathbb {Z} }</annotation></semantics></math>
에 대하여, 만약 <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\in S}"><semantics><annotation encoding="application/x-tex">{\displaystyle n\in S}</annotation></semantics></math>
라면, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n+1\in S}"><semantics><annotation encoding="application/x-tex">{\displaystyle n+1\in S}</annotation></semantics></math>
그렇다면,
<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{n\in \mathbb {Z} \colon n\geq m\}\subseteq S}"><semantics><annotation encoding="application/x-tex">{\displaystyle \{n\in \mathbb {Z} \colon n\geq m\}\subseteq S}</annotation></semantics></math>
이다. 즉, 임의의
<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\in \mathbb {Z} }"><semantics><annotation encoding="application/x-tex">{\displaystyle n\in \mathbb {Z} }</annotation></semantics></math>
(
<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\geq m}"><semantics><annotation encoding="application/x-tex">{\displaystyle n\geq m}</annotation></semantics></math>
)에 대하여,
<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\in S}"><semantics><annotation encoding="application/x-tex">{\displaystyle n\in S}</annotation></semantics></math>
이다. 수학적 귀납법은 여기서
<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m=0,1}"><semantics><annotation encoding="application/x-tex">{\displaystyle m=0,1}</annotation></semantics></math>
인 특수한 경우이다.
역진 귀납법[편집]
자연수
<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m\in \mathbb {N} }"><semantics><annotation encoding="application/x-tex">{\displaystyle m\in \mathbb {N} }</annotation></semantics></math>
이 주어졌을 때, 임의의 자연수 부분 집합
<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S\subseteq \mathbb {N} }"><semantics><annotation encoding="application/x-tex">{\displaystyle S\subseteq \mathbb {N} }</annotation></semantics></math>
이 다음 두 조건을 만족시킨다고 하자.
- <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m\in S}"><semantics><annotation encoding="application/x-tex">{\displaystyle m\in S}</annotation></semantics></math>

- 임의의 <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\in \mathbb {N} }"><semantics><annotation encoding="application/x-tex">{\displaystyle n\in \mathbb {N} }</annotation></semantics></math>
에 대하여, 만약 <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n+1\in S}"><semantics><annotation encoding="application/x-tex">{\displaystyle n+1\in S}</annotation></semantics></math>
라면, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\in S}"><semantics><annotation encoding="application/x-tex">{\displaystyle n\in S}</annotation></semantics></math>
그렇다면,
<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{n\in \mathbb {N} \colon n\leq m\}\subseteq S}"><semantics><annotation encoding="application/x-tex">{\displaystyle \{n\in \mathbb {N} \colon n\leq m\}\subseteq S}</annotation></semantics></math>
이다. 즉, 임의의
<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\in \mathbb {N} }"><semantics><annotation encoding="application/x-tex">{\displaystyle n\in \mathbb {N} }</annotation></semantics></math>
(
<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\leq m}"><semantics><annotation encoding="application/x-tex">{\displaystyle n\leq m}</annotation></semantics></math>
)에 대하여,
<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\in S}"><semantics><annotation encoding="application/x-tex">{\displaystyle n\in S}</annotation></semantics></math>
이다.
초한 귀납법[편집]
임의의 자연수 부분 집합
<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S\subseteq \mathbb {N} }"><semantics><annotation encoding="application/x-tex">{\displaystyle S\subseteq \mathbb {N} }</annotation></semantics></math>
이 다음 조건을 만족시킨다고 하자.
- 임의의 <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\in \mathbb {N} }"><semantics><annotation encoding="application/x-tex">{\displaystyle n\in \mathbb {N} }</annotation></semantics></math>
에 대하여, 만약 <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle" \{k\in \mathbb {N} \colon k><n>\}\subseteq S}"><semantics><annotation encoding="application/x-tex">{\displaystyle \{k\in \mathbb {N} \colon k<n\}\subseteq S}</annotation></semantics></math>
라면, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\in S}"><semantics><annotation encoding="application/x-tex">{\displaystyle n\in S}</annotation></semantics></math>
이다.
(특히,
<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=0}"><semantics><annotation encoding="application/x-tex">{\displaystyle n=0}</annotation></semantics></math>
일 경우 이는
<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0\in S}"><semantics><annotation encoding="application/x-tex">{\displaystyle 0\in S}</annotation></semantics></math>
를 뜻한다.) 그렇다면,
<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S=\mathbb {N} }"><semantics><annotation encoding="application/x-tex">{\displaystyle S=\mathbb {N} }</annotation></semantics></math>
이다. 즉, 임의의
<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\in \mathbb {N} }"><semantics><annotation encoding="application/x-tex">{\displaystyle n\in \mathbb {N} }</annotation></semantics></math>
에 대하여,
<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\in S}"><semantics><annotation encoding="application/x-tex">{\displaystyle n\in S}</annotation></semantics></math>
이다. 이를 자연수 집합 위의
초한 귀납법이라고 하며,
제2/강한/완전 수학적 귀납법이라고도 한다.
보다 일반적으로,
정초 관계 <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sim _{R}}"><semantics><annotation encoding="application/x-tex">{\displaystyle \sim _{R}}</annotation></semantics></math>
를 갖춘
집합 <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}"><semantics><annotation encoding="application/x-tex">{\displaystyle X}</annotation></semantics></math>
의 부분 집합
<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S\subseteq X}"><semantics><annotation encoding="application/x-tex">{\displaystyle S\subseteq X}</annotation></semantics></math>
가 다음 조건을 만족시킨다고 하자.
- 임의의 <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in X}"><semantics><annotation encoding="application/x-tex">{\displaystyle x\in X}</annotation></semantics></math>
에 대하여, 만약 <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{y\in X\colon y\sim _{R}x\}\subseteq S}"><semantics><annotation encoding="application/x-tex">{\displaystyle \{y\in X\colon y\sim _{R}x\}\subseteq S}</annotation></semantics></math>
라면, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in S}"><semantics><annotation encoding="application/x-tex">{\displaystyle x\in S}</annotation></semantics></math>
이다.
그렇다면,
<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S=X}"><semantics><annotation encoding="application/x-tex">{\displaystyle S=X}</annotation></semantics></math>
이다. 즉, 임의의
<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in X}"><semantics><annotation encoding="application/x-tex">{\displaystyle x\in X}</annotation></semantics></math>
에 대하여,
<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in S}"><semantics><annotation encoding="application/x-tex">{\displaystyle x\in S}</annotation></semantics></math>
이다.
그 밖에도 수학적 귀납법과 비슷한 증명법이 많이 존재한다. 예를 들어, 임의의 자연수 부분 집합
<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S\subseteq \mathbb {N} }"><semantics><annotation encoding="application/x-tex">{\displaystyle S\subseteq \mathbb {N} }</annotation></semantics></math>
이 다음 두 조건을 만족시킨다고 하자.
- <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0,1\in S}"><semantics><annotation encoding="application/x-tex">{\displaystyle 0,1\in S}</annotation></semantics></math>

- 임의의 <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\in \mathbb {N} }"><semantics><annotation encoding="application/x-tex">{\displaystyle n\in \mathbb {N} }</annotation></semantics></math>
에 대하여, 만약 <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\in S}"><semantics><annotation encoding="application/x-tex">{\displaystyle n\in S}</annotation></semantics></math>
라면, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n+2\in S}"><semantics><annotation encoding="application/x-tex">{\displaystyle n+2\in S}</annotation></semantics></math>
또는, 다음 두 조건을 만족시킨다고 하자.
- <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0\in S}"><semantics><annotation encoding="application/x-tex">{\displaystyle 0\in S}</annotation></semantics></math>

- 임의의 <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\in \mathbb {N} }"><semantics><annotation encoding="application/x-tex">{\displaystyle n\in \mathbb {N} }</annotation></semantics></math>
에 대하여, 만약 <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\in S}"><semantics><annotation encoding="application/x-tex">{\displaystyle n\in S}</annotation></semantics></math>
라면, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2n,2n+1\in S}"><semantics><annotation encoding="application/x-tex">{\displaystyle 2n,2n+1\in S}</annotation></semantics></math>
그렇다면,
<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S=\mathbb {N} }"><semantics><annotation encoding="application/x-tex">{\displaystyle S=\mathbb {N} }</annotation></semantics></math>
이다. 즉, 임의의
<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\in \mathbb {N} }"><semantics><annotation encoding="application/x-tex">{\displaystyle n\in \mathbb {N} }</annotation></semantics></math>
에 대하여,
<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\in S}"><semantics><annotation encoding="application/x-tex">{\displaystyle n\in S}</annotation></semantics></math>
이다.
수학적 귀납법보다 약한 명제[편집]
페아노 공리계에서 수학적 귀납법을 제외하여 얻는 이론 아래, 다음 두 명제가 서로 동치이다.
수학적 귀납법은 이 세 명제를 함의하지만, 이 세 명제는 수학적 귀납법을 함의하지 않는다. 예를 들어, 다음과 같은 대상들로 이루어진
구조는 자연수의 정렬성 및 초한 귀납법 및 무한 강하법을 만족시키지만, 수학적 귀납법을 만족시키지 않으므로 페아노 공리게의
모형이 아니다.
- 집합 <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{0,0.5,1,1.5,\dots \}}"><semantics><annotation encoding="application/x-tex">{\displaystyle \{0,0.5,1,1.5,\dots \}}</annotation></semantics></math>

- 상수 <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0}"><semantics><annotation encoding="application/x-tex">{\displaystyle 0}</annotation></semantics></math>

- 단항 연산 <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (-)+1}"><semantics><annotation encoding="application/x-tex">{\displaystyle (-)+1}</annotation></semantics></math>

수학적 귀납법과 동치인 명제[편집]
페아노 공리계에서 수학적 귀납법을 제외하여 얻는 이론 아래, 다음 두 명제가 서로 동치이다.
- 수학적 귀납법
- 다음 두 명제의 논리곱
- 자연수의 정렬성 (또는 초한 귀납법 또는 무한 강하법)
- <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {N} \setminus \{0\}\subseteq \mathbb {N} +1}"><semantics><annotation encoding="application/x-tex">{\displaystyle \mathbb {N} \setminus \{0\}\subseteq \mathbb {N} +1}</annotation></semantics></math>
. 즉, 모든 0이 아닌 자연수는 어떤 자연수 더하기 1이다.
모든 자연수가 어떤 성질을 만족시킨다는 명제에 대한 수학적 귀납법을 통한 증명은 다음과 같은 두 단계로 구성된다.
- 처음 오는 자연수(0 또는 1)에 대한 증명
- <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"><semantics><annotation encoding="application/x-tex">{\displaystyle n}</annotation></semantics></math>
이 만족시킨다는 가정 아래, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n+1}"><semantics><annotation encoding="application/x-tex">{\displaystyle n+1}</annotation></semantics></math>
에 대한 증명
자연수와 관련된 수많은
항등식 ·
부등식 ·
기하학 정리 따위를 이러한 단계들을 거쳐 증명할 수 있다.
홀수의 합 공식[편집]
- <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1+3+5+\cdots +(2n-1)=n^{2}}"><semantics><annotation encoding="application/x-tex">{\displaystyle 1+3+5+\cdots +(2n-1)=n^{2}}</annotation></semantics></math>

이 임의의 자연수
<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"><semantics><annotation encoding="application/x-tex">{\displaystyle n}</annotation></semantics></math>
에 대하여 성립한다는 사실을 다음과 같이 증명할 수 있다.
- 1에 대하여 성립
- 1에 대한 공식 <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1=1^{2}}"><semantics><annotation encoding="application/x-tex">{\displaystyle 1=1^{2}}</annotation></semantics></math>
은 자명하게 성립한다.
- <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"><semantics><annotation encoding="application/x-tex">{\displaystyle n}</annotation></semantics></math>
에 대하여 성립한다는 가정 아래, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n+1}"><semantics><annotation encoding="application/x-tex">{\displaystyle n+1}</annotation></semantics></math>
에 대하여 성립
- <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"><semantics><annotation encoding="application/x-tex">{\displaystyle n}</annotation></semantics></math>
에 대하여 성립하므로, 다음이 성립한다.
- <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1+3+5+\cdots +(2n-1)=n^{2}}"><semantics><annotation encoding="application/x-tex">{\displaystyle 1+3+5+\cdots +(2n-1)=n^{2}}</annotation></semantics></math>

- 양변에 <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2n+1}"><semantics><annotation encoding="application/x-tex">{\displaystyle 2n+1}</annotation></semantics></math>
를 더하면, 다음과 같다.
- <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1+3+5+\cdots +(2n-1)+(2(n+1)-1)=n^{2}+2n+1=(n+1)^{2}}"><semantics><annotation encoding="application/x-tex">{\displaystyle 1+3+5+\cdots +(2n-1)+(2(n+1)-1)=n^{2}+2n+1=(n+1)^{2}}</annotation></semantics></math>

- 이에 따라, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n+1}"><semantics><annotation encoding="application/x-tex">{\displaystyle n+1}</annotation></semantics></math>
에 대하여 성립한다.
수학적 귀납법에 따라, 임의의
<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\in \mathbb {N} }"><semantics><annotation encoding="application/x-tex">{\displaystyle n\in \mathbb {N} }</annotation></semantics></math>
에 대하여, 홀수의 합 공식이 성립한다.
빨간 눈 퍼즐[편집]
어떤 섬의 사람들에게 다음과 같은 조건이 주어졌다고 하자.
- 각 섬사람은 빨간 눈을 갖거나, 파란 눈을 갖는다.
- 각 섬사람은 자신을 제외한 이들의 눈 색을 안다.
- 각 섬사람은 거울을 볼 수 없으며, 다른 이들에게 자신의 눈 색을 물을 수 없다.
- 자신이 빨간 눈임을 알게 된 섬사람은 그날 밤 섬을 떠나야 한다.
- 어느 날 아침에 이방인이 찾아와 섬사람들 중에 빨간 눈이 있다는 말을 흘렸다.
- 다음과 같은 지식들은 섬사람들 사이에서 공유 지식이다. (즉, 사실이며, 모두가 알며, 모두가 앎을 모두가 알며, ...)
- 모든 구성원의 사고력은 충분히 뛰어나다.
- 이방인은 정직하다.
그렇다면, 빨간 눈을 가진 섬사람의 수가
<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"><semantics><annotation encoding="application/x-tex">{\displaystyle n}</annotation></semantics></math>
이라면, 모든 빨간 눈은 이방인이 찾아온 날부터 세어
<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"><semantics><annotation encoding="application/x-tex">{\displaystyle n}</annotation></semantics></math>
번째 날 밤에 섬을 떠나게 되며, 이를 수학적 귀납법을 통해 증명할 수 있다. 이방인은 (
<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n>1}"><semantics><annotation encoding="application/x-tex">{\displaystyle n>1}</annotation></semantics></math>
이라면) 모두가 알고 있는 뻔한 사실을 말했을 뿐이지만, 평소와는 다른 특별한 결과를 가져왔다.
최초로 수학적 귀납법이 사용된 예는
유클리드의 소수의 무한성에 대한 증명이나
바스카라 2세의 "순환 방법"(cyclic method) 등에서 찾을 수 있다.".
[1] 알카라지는 1000년 경에 쓴 책에서
이항 정리 등을 증명하기 위해 수학적 귀납법의 한 형태를 사용했다.
[2] [3] 그러나 이들은 수학적 귀납법을 자신이 사용한 가정으로서 명확히 밝히지 않았으며, 처음으로 귀납법에 대한 엄밀한 서술을 한 이는
프란체스코 마우롤리코 (Francesco Maurolico)로, 그는 1575년의 저서 〈Arithmeticorum libri duo〉에서 이를 이용해 가장 작은 n개의 홀수를 더하면 n
2이 됨을 증명했다. 스위스의
야코프 베르누이와 프랑스의
블레즈 파스칼 및
피에르 드 페르마도 귀납법을 독립적으로 발견했다.
[1]
Wikipedia
댓글 없음:
댓글 쓰기