수학적 귀납법

증명법은 크게 연역법과 귀납법이 있음을 배웠다. 거칠게 말하자면 연역법은 3단 논법처럼 참임이 증명된 명제로부터 주어진 새로운 명제가 참임을 밝히는 증명법이다. 반면 귀납법은 각각의 사례를 바탕으로 일반적인 원리를 이끌어 내는 증명법이다.

아래와 같은 흔한 예가 있다.

연역법(deduction)

$p\Rightarrow q$: 사람은 죽는다. 

$r\Rightarrow p$: 소크라테스는 사람이다.

$r\Rightarrow q$: 그러므로 소크라테스는 죽는다.

귀납법(induction)

사례 1: 플라톤은 죽었다.

사례 2: 소크라테스도 죽었다.

사례 3: 아리스토텔레스도 죽었다.

결론: 모든 사람은 죽는다.

수학은 매우 연역적인 학문이라 귀납법을 좀처럼 인정하지 않는다. 혹시 아직 그런 사람은 없지만 죽지 않고 영생하는 사람이 나타날 가능성은 없을까를 고민하는 것이 수학이다. 아직까지는 영생은 사이비 교주나 떠드는 말이긴 하지만 말이다.

인덕션(Induction)과 디덕션(Deduction)은 모두 '이끌다'라는 뜻의 라틴어 동사 두케레(Dūcere)에 접두사가 결합하여 만들어진 단어이다. 접두사에 따라 '어디로 이끄느냐'의 방향성이 달라진다.

1. 인덕션 (Induction)의 라틴어 어원: Inductio

* 어원 구조: 안으로(In-) + 이끌다(Dūcere) = 인두케레(Indūcere)

* 명사형: 인둑티오(Inductio)

* 어원적 의미: '안으로 이끌어 들임'을 뜻한다.

* 학술적 배경: 로마의 철학자 키케로(Cicero)가 그리스 철학자 아리스토텔레스의 귀납법 개념인 '에파고게(Epagoge, 인도하다)'를 라틴어로 번역하면서 인둑티오(Inductio)라는 말을 처음 사용했다. 개별적인 사례들을 머릿속으로 '이끌어 들여' 하나의 법칙을 만든다는 뜻이다. 

2. 디덕션 (Deduction)의 라틴어 어원: Deductio

* 어원 구조: 아래로/밖으로(De-) + 이끌다(Dūcere) = 데두케레(Dedūcere)

* 명사형: 데둑티오(Deductio) * 어원적 의미: '아래로 이끌어 내림' 또는 '출발지로부터 잡아끎'을 뜻한다.

* 학술적 배경: 이미 확립된 거대한 일반 원리(위)로부터 구체적인 결론(아래)을 '밑으로 이끌어 내린다'는 사고 과정에서 유래했다. 결론을 아래로 도출해내는(Derive) 연역법의 성격을 그대로 담고 있다.

이 외에도 두케레(Dūcere, 이끌다)에서 파생된 다른 학술 용어(예: Abduction(가추법), Reduction(환원) 등)가 있다.  

 

왜 새로운 증명 방법이 필요한가?

홀수를 차례로 더한 값을 구한다고 하자.

$$1+3+5+\cdots +(2n-1)$$

연역법은 등차수열의 합을 이용하는 것이다.

$$\begin{split}S=&1&+&3&+&5&+\cdots +&(2n-3)&+&(2n-1)&\\S=&(2n-1)&+&(2n-3)&+&(2n-5)&+\cdots+&3&+&1&\end{split}$$

$$2S=n\times(2n)$$

$$\therefore\;\;S=n^2$$

귀납법은 아래와 같이 추측해 보는 것이다.

$$\begin{split}1=1^2\\1+3=4=2^2\\1+3+5=9=3^2\\1+3+5+7=16=4^2\\\vdots\quad\end{split}$$

느낌으로 아래와 같음을 예상할 수 있다.

$$1+3+5+\cdots +(2n-1)=n^2\tag{1}$$

(1)은 아래와 같은 그림으로 나타낸 사각수를 활용하여 추측할 수 있다.

아무튼 (1)은 $n=1, 2, 3, 4$를 대입해 보면 맞다. 또한 이후로 아무리 많은 값을 확인해도 모두 참이다. 그러나 (1)이 모든 자연수에 대하여 참이라는 추측은 될 수 있어도 수학적인 증명은 될 수 없다. 따라서 더 엄밀한 방법이 필요하다. 

이때 어떤 자연수 이후로 있는 모든 자연수에 대해 한 번에 증명하는 방법을 수학적 귀납법(mathmatical induction)이라고 한다. 앞에 수학적이란 수식어가 달린 까닭을 이해해야 한다.

도미노 놀이

도미노가 길게 세워져 있다고 생각해 보자.

• 첫 번째 도미노가 넘어짐
• 어떤 도미노가 넘어지면 그다음 도미노도 반드시 넘어지도록 세움.

이 두 조건이 만족되어야 모든 도미노가 넘어진다. 수학적 귀납법도 정확히 같은 구조이다. 두 조건 가운데 어느 하나라도 만족하지 않으면 모든 도미노가 쓰러질 수 없다.

수학적 귀납법의 두 단계

(1) 첫 단계

명제 $P(n)$이 있을 때, $P(1)$이 참임을 보임.

→ 첫 번째 도미노를 넘어뜨림.

(2) 귀납 단계

$P(k)$가 참이라고 가정하고 $P(k+1)$도 참임을 보임.

→ $k$번째 도미노가 넘어지면 다음 도미노도 넘어지도록 세웠다는 것을 뜻함.

왜 이것이 모든 자연수에 대해 참이 되는가?

• $P(1)$ 참
• 따라서 $P(2)$ 참
• 따라서 $P(3)$ 참
• 따라서 $P(4)$ 참
• $\cdots$

결국 모든 자연수 $n$에 대해 참이다.

대표 예제

$$1+2+3+\cdots+n=\frac{n(n+1)}{2}\tag{2}$$

i) 첫 단계

$n=1$일 때, 

좌변$=1=\displaystyle{\frac{1(1+1)}{2}}=$우변

이므로 (2)가 성립한다.

ii) $n=k$일 때 성립함을 가정하면

$$1+2+\cdots+k=\frac{k(k+1)}{2}\tag{3}$$

(3)의 양변에 $k+1$을 더하여 정리하면

$$\begin{split}1+2+\cdots+k+(k+1)=\frac{k(k+1)}{2}+(k+1)\\=\frac{(k+1)(k+2)}{2}\\=\frac{(k+1)\{(k+1)+1\}}{2}\end{split}$$

이다. 따라서 $n=k+1$일 때도 성립한다.

i)과 ii)에 따라서 모든 자연수 $n$에 대해 성립한다.

학생들이 가장 많이 하는 실수

① $P(1)$이 참인 이유를 빠트림. → 도미노는 세웠으나 첫 째 도미노를 쓰러뜨리지 않음.

② 귀납 가정을 마치 결론처럼 사용

③ $P(k+1)$이 참임을 보여야 하는데 중간 계산만 하고 끝냄.

④ 마지막에 "따라서 모든 자연수 $n$에 대해 성립한다."를 쓰지 않음.

핵심 정리

수학적 귀납법은

• 첫 번째 경우가 참이고
• 한 단계에서 다음 단계로 참이 전달됨을 보이면

모든 자연수에 대해 참임을 증명하는 방법이다.

즉, "첫 번째 도미노를 쓰러뜨리고, 도미노 사이의 연결을 확인하는 증명법"이라고 이해하면 된다.

마지막으로 수학적 귀납법은 반드시 자연수와 관련된 명제를 증명할 때만 사용해야 한다는 것이다.

i) 머리카락 개수가 1인 사람은 대머리이다.

ii) 머리카락  개수가 $k$인 사람이 대머리라면

$k+1$인 사람도 대머리이다.

i), ii)에 따라서 머리카락 개수가 자연수 $n$인 모든 사람은 모두 대머리이다.

마무리 연습

실제로 증명을 할 때 그냥 같은 식을 되풀이해서 쓰는 것처럼 느껴진다면 아직 이해가 덜 된 것이다. 등식을 쉽게 증명하는 학생도 때로는 부등식은 조금 어려워하기도 한다. 이는 귀납 단계에서 $n=k$와 $n=k+1$일 때 식의 차를 구해봄으로써 쉽게 해결할 수 있다.

등식

$$1\times2+2\times3+3\times 4+\cdots+n(n+1)=\frac{1}{3}n(n+1)(n+2)$$

i) $n=1$일 때

좌변$=1\times2=2=\displaystyle{\frac{1}{3}\times1\times2\times3}=$우변

이므로 주어진 등식이 성립

ii) $n=k$일 때 주어진 등식이 성립한다고 가정하면

$$1\times2+2\times3+3\times 4+\cdots+k(k+1)=\frac{1}{3}k(k+1)(k+2)$$

이 등식의 양변에 $(k+1){k+2)$를 더하면

$$1\times2+2\times3+3\times 4+\cdots+k(k+1)+(k+1)(k+2)=\frac{1}{3}k(k+1)(k+2)+(k+1)(k+2)$$

(이미 좌변은 $n=k+1$일 때의 모양이 되었으므로 우변만 고치는 과정을 보이면 된다. 이 경우는 인수분해만 해도 쉽게 정리된다.)

$$\begin{split}\frac{1}{3}k(k+1)(k+2)+(k+1)(k+2)=\frac{1}{3}(k+1)(k+2)(k+3)\\=\frac{1}{3}(k+1)((k+1)+1)((k+1)+2)\end{split}$$

(너무 쉬워서 굳이 보일 필요조차 없어 보인다. 마지막으로 잊지말고 결론을 반드시 적어야 한다.)

i)과 ii)에 따라서 모든 자연수 $n$에 대하여 주어진 등식이 성립한다.

부등식

다음으로 부등식을 연습해 보자. 아래는 베르누이 부등식으로 불리는 유명한 부등식이다.

$h>0$일 때, $n \geq 2$인 모든 자연수 $n$에 대하여 $$(1+h)^n>1+nh$$

i) $n=2$일 때

좌변$=(1+h)^2=1+2h+h^2>1+2h=$우변

이므로 주어진 부등식이 성립한다.

$(1+2h+h^2)-(1+2h)=h^2>0$이므로 자연스럽게 부등호가 성립함을 보인 것이다. 이처럼 부등호가 성립함을 보이는 가장 쉬운 방법은 차를 구해 부호를 알아보는 것이다.

ii) $n=k$일 때 $(1+h)^k>1+kh$라고 하자.

먼저 좌변을 $n=k+1$일 때 모양으로 바꿔야 한다. 따라서 양변에 $1+h>0$을 곱한다.

$$\underbrace{(1+h)^{k+1}}_{n=k+1일\;때\;우변}>(1+kh)(1+h)\tag{5-1}$$

이제 우변을 바꾸는 과정을 보인다.

$$\begin{split}(1+kh)(1+h)=1+(k+1)h+kh^2\\>1+(k+1)h+kh^2-kh^2\\=\underbrace{1+(k+1)h}_{n=k+1일\;때\; 좌변}\end{split}\tag{5-2}$$

여기서도 마찬가지로 $(1+(k+1)h+kh^2)-(1+(k+1)h)=kh^2>0$임을 이용한 것이다.

i)과 ii)에 따라서 $n\geq 2$인 모든 자연수 $n$에 대하여 주어진 등식이 성립한다.

보통 (5-1)과 (5-2)를 아래와 같이 당연한 부분을 생략하고 한꺼번에 적기 때문에 실력이 낮은 학생은 쉽게 이해하지 못한다.

$$\begin{split}\underbrace{(1+h)^{k+1}}_{n=k+1일\;때\;우변}>(1+kh)(1+h)\\=1+(k+1)h+kh^2\\>\underbrace{1+(k+1)h}_{n=k+1일\;때\; 좌변}\end{split} $$

참고: 이 부등식의 좌변은 복리계산, 우변은 단리계산에 해당한다. 등비수열의 항과 등차수열의 항을 비교하면 당연히 등비수열의 항이 더 크다.

명심하자. 귀납단계는 필요한 모양($n=k+1$)을 먼저 생각하고 가정한 단계($n=k$)와 차이를 구하는 것으로 이해하는 연습을 하자.

 

 

https://suhak.tistory.com/242

새로운 방법으로 표현된 산술 원리