수학적 귀납법

원문 보기: https://dawoum.duckdns.org/wiki/수학적_귀납법

See also: Mathematical induction

수학적 귀납법(Mathematical induction)은 수학적 증명 기법입니다. 이것은 속성 P(n)이 모든 자연수 n, 즉 n = 0, 1, 2, 3,  등에 대해 성립한다는 것을 증명하기 위해서 필수적으로 사용됩니다.

은유적 표현, 연속적으로 넘어지는 도미노 또는 사다리 오르는 것의 은유와 같은 것은, 수학적 귀납법의 개념을 이해하기 위해서 비공식적으로 사용될 수 있습니다.

수학적 귀납법은, 우리가 밑바닥 가로장 (기초) 위로 올라갈 수 있다는 것을 증명하고 각 가로장에서 다음 가로장 (귀납적 단계)으로 올라갈 수 있음을 증명함으로써, 우리가 사다리에서 원하는 만큼 높이 올라갈 수 있다는 것을 증명할 수 있습니다.
— Concrete Mathematics, page 3 margins.

귀납법의 방법은 증명해야 할 두 경우를 요구합니다. 기본 경우(base case) (또는, 때때로 기초(basis))라고 불리는, 첫 번째 경우는 속성이 숫자 0에 대해 유지된다는 것을 증명합니다. 귀납법 단계(induction step)라고 불리는, 두 번째 경우는, 만약 속성이 하나의 자연수 n에 대해 유지되면, 그것은 다음 자연수 n + 1에 대해 유지됨을 증명합니다. 이러한 두 단계는 모든 자연수 n = 0, 1, 2, 3, ...에 대해 속성 P(n)을 확증합니다. 기본 경우는 영으로 시작할 필요가 없습니다. 흔히 그것은 숫자 일로 시작하고, 그것이 임의의 자연수로 시작하여, 시작 번호보다 크거나 같은 모든 자연수에 대한 속성의 참을 확증할 수 있습니다.

학교에서는 자연수가 1부터 시작하는 것으로 배우지만, 0을 포함하는 경우와 0을 포함하지 않는 경우로 나뉩니다. 자세한 것은 기사 자연수를 참조하십시요. 이 기사에서, 자연수는 1부터 시작합니다.

예를 들어, 양의 홀수로 이루어진 수열의 처음 n번째 항까지의 합을 \(S_n\)이라 하면

\(\quad\)\(S_n=1+3+5+7+\cdots+(2n-1)\)

여기서 \(n=1,2,3,\cdots\)을 차례로 대입해서 \(S_1,S_2,S_3,\cdots\)을 구해 보면

\(\quad\)\(S_1=1=1^2\)

\(\quad\)\(S_2=1+3=4=2^2\)

\(\quad\)\(S_3=1+3+5=9=3^2\)

\(\quad\)\(\qquad\vdots\)

따라서 항의 개수가 n개이면 다음과 같이 추론할 수 있습니다.

\(\quad\)\(S_n=1+3+5+\cdots+(2n-1)=n^2\)

그러나, 이 추론으로는 위 식이 반드시 성립하는 것을 증명했다고 말할 수는 없습니다. 그래서 사용하는 방법이 수학적 귀납법입니다.

다음과 같은 명제를 수학적 귀납법으로 증명하는 과정은 아래와 같습니다.

명제: 모든 자연수 n에 대해 다음 등식이 항상 성립합니다.

\(\quad\)\(S_n=1+3+5+\cdots+(2n-1)=n^2\quad\cdots (1)\)

기본 경우: n= 1일 때, \(S_1=1=1^2\)이므로 성립합니다.

귀납적 단계: n = k일 때, 다음 식이 성립한다고 가정합니다.

\(\quad\)\(S_k=1+3+5+\cdots+(2k-1)=k^2\)

이 식의 양변에 그다음의 홀수, 즉, \((2k-1)+2\)를 더하면,

\(\quad\)\(1+3+5+\cdots+(2k-1)+(2k+1)=k^2+2k+1=(k+1)^2=S_{k+1}\)

따라서 \(n=k+1\)일 때, 위 식이 성립합니다. 그러므로, 기본 경우와 귀납적 단계에 의해서 (1)이 모든 자연수에 대해 성립합니다.

증명에서, 주목할 것은 귀납적 단계에서 n = k + 1일 때 성립함을 보이는 것입니다. 이를 위해서는 주어진 명제의 특징을 이용해야 합니다. 위의 명제에서는 그다음의 홀수를 더하는 것이었습니다. 예를 들어, 모든 자연수에 대해서 성립하는 다음 명제를 생각해 보십시오.

\(\quad\)\(1+3+3^2+\cdots+3^{n-1}=\frac{1}{2}\left(3^n-1\right)\)

이 명제는 3의 거듭제곱을 0부터 \(n-1\)개 더하는 것입니다. 따라서 귀납적 단계에서는 양변에 \(3^k\)를 더해서 우변의 모양이 \(\displaystyle \frac{1}{2}\left(3^{k+1}-1\right)\)이 됨을 보임으로써 증명이 끝납니다. 위의 두 예제는 왼쪽 변의 모양을 먼저 맞추고 우변이 \(k+1\)의 모양이 됨을 맞춥니다. 어쨌든, 때때로 우변의 모양을 먼저 맞추고, 왼쪽 변이 그다음 항의 것으로 만드는 경우도 있습니다.

부등식의 경우

부등식을 포함하는 명제를 수학적 귀납법으로 증명하는 과정입니다.

명제 : \(h>0\)일 때, \(n\geq 2\)인 모든 자연수 \(n\)에 대해 다음 부등식이 성립함을 수학적 귀납법으로 증명하십시오.

\(\quad\)\((1+h)^n > 1+nh\)

기본 경우 : \(n=2\)일 때, \((1+h)^2 > 1+2h\)이고, \(h^2>0\)이므로 성립합니다.

귀납적 단계 : \(n=k\)일 때 다음이 성립한다고 가정합니다.

\(\quad\)\((1+h)^k > 1+kh\)

여기서 양변에 \((1+h)\)를 곱하면, 

\(\quad\)\((1+h)^{k+1} > (1+kh)(1+h)\quad\cdots (2)\)

이 식은 왼쪽 변은 명제의 왼쪽 변의 모양으로 바뀌었지만, 오른쪽 변은 명제의 오른쪽 변의 모양을 만족하지는 않습니다.

게다가, 다음 식이 성립합니다.

\(\quad\)\((1+kh)(1+h)=1+kh+h+kh^2=1+(k+1)h+kh^2>1+(k+1)h\quad\cdots (3)\)

왜냐하면 \(kh^2>0\)이기 때문입니다.

따라서, 식 (2)와 (3)을 비교하면, 다음이 성립합니다.

\(\quad\)\((1+h)^{k+1} > 1+(k+1)h\)

그러므로, 명제의 증명은 끝났습니다.

한편, 위의 증명도 왼쪽 변을 먼저 맞추는 형식입니다. 만약 오른쪽을 먼저 맞추는 형태로 귀납적 단계를 수행할 수 있습니다:

귀납적 단계 : \(n=k\)일 때 다음이 성립한다고 가정합니다.

\(\quad\)\((1+h)^k > 1+kh\)

여기서 양변에 \(h\)를 더하면, 

\(\quad\)\((1+h)^k+h > (1+kh)+h=1+(k+1)h\quad\cdots (4)\)

게다가, 다음 식이 성립합니다.

\(\quad\)\((1+h)^{k+1}=(1+h)^k(1+h)=(1+h)^k+h(1+h)^k>(1+h)^k+h\quad\cdots (5)\)

왜냐하면, \((1+h)^k>1\)이기 때문입니다.

따라서, 식 (4)와 (5)을 비교하면, 다음이 성립합니다.

\(\quad\)\((1+h)^{k+1} > 1+(k+1)h\)

그러므로, 명제의 증명은 끝났습니다.

응용예제

응용예제1

상수 \(k\;(k>1)\)에 대하여 다음 조건을 만족시키는 수열 \(\{a_n\}\)이 있다.

모든 자연수 \(n\)에 대하여 \(a_n < a_{n+1}\)이고
곡선 \(y=2^x\) 위의 두 점 \(\mathrm P_n\left(a_n,2^{a_n}\right), \mathrm P_{n+1}\left(a_{n+1},2^{a_{n+1}}\right)\)을
지나는 직선의 기울기는 \(k\times 2^{a_n}\)이다.

점 \(\rm P_n\)을 지나고 \(x\)축에 평행한 직선과 점 \(\rm P_{n+1}\)을 지나고 \(y\)축에 평행한 직선이 만나는 점을 \(\rm Q_n\)이라 하고 삼각형 \(\rm P_n \rm Q_n \rm P_{n+1}\)의 넓이를 \(A_n\)이라 하자.

다음은 \(a_1=1,\;\frac{A_3}{A_1}=16\)일 때, \(A_n\)을 구하는 과정이다.

두 점 \(\rm P_n,\;\rm P_{n+1}\)을 지나는 직선의 기울기가 \(k\times 2^{a_n}\)이므로
\(\quad\)\(2^{a_{n+1}-a_n}=k\left(a_{n+1}-a_n\right)+1\)
이다. 즉, 모든 자연수 \(n\)에 대하여 \(a_{n+1}-a_n\)은
방정식 \(2^x=kx+1\)의 해이다.
\(k>1\)이므로 방정식 \(2^x=kx+1\)은 오직 하나의 양의 실근
\(d\)를 갖는다. 따라서 모든 자연수 \(n\)에 대하여
\(a_{n+1}-a_n=d\)이고, 수열 \(\{a_n\}\)은 공차가 \(d\)인 등차수열이다.
점 \(\rm Q_n\)의 좌표가 \(\left(a_{n+1},\;2^{a_n}\right)\)이므로
\(\quad\)\(A=\frac{1}{2}\left(a_{n+1}-a_n\right)\left(2^{a_{n+1}}-2^{a_n}\right)\)
이다. \(\frac{A_3}{A_1}=6\)이므로 \(d\)의 값은 (가)이고,
수열 \(\{a_n\}\)의 일반항은
\(\quad\)\(a_n=\)(나)
이다. 따라서 모든 자연수 \(n\)에 대하여 \(A_n=\)(다)이다.

위의 (가)에 알맞은 수를 \(p\), (나)와 (다)에 알맞은 식을 각각 \(f(n),\;g(n)\)이라 할 때, \(\displaystyle p+\frac{g(4)}{f(2)}\)의 값은? [4점] [2021학년도 수능 가형 16번]