수학적 귀납법

수학적 귀납법은 수학에서 자주 쓰는 증명 방법이다. 주로 자연수나 다른 어떤 수열을 다룰 때 쓴다.

원리

기본 원리는 다음과 같다. 먼저 주어진 주장을 첫 번째 원소에 대해 증명한다. 자연수에서는 대개 n = 1이다. 첫 번째 원소에 대해서는 대입만 하면 증명된다. 그다음 귀납 단계에서는 “주장이 n = a일 때 성립하면 n = a + 1일 때도 성립한다”라는 조건문을 증명한다.

이 두 단계에서 주어진 식이 (다루고 있는 집합의) 모든 n에 대해 성립한다는 것을 이끌어 낼 수 있다. 왜 그럴까? 처음에 식이 n = 1일 때 성립함을 증명한다. 또 식이 n = a일 때 성립하면 n = a + 1일 때도 성립한다는 것도 안다. 그래서 a = 1로 놓는다. a = 1일 때 식이 성립하므로 a + 1 = 2일 때도 성립한다. 이제 식이 a = 2일 때 성립한다는 것을 안다. 그러면 a + 1일 때도 성립하므로 2 + 1 = 3일 때도 성립해야 한다. 이런 식으로 계속된다.

첫 번째 예제

첫 번째 예제는 자명하다. 어떤 짝수에 2를 더해도 다시 짝수가 된다는 것을 증명하자. 자연수를 다루고 있으므로 짝수를 일반적으로 2n으로 쓴다. 여기서 n은 자연수이다. n에 어떤 자연수를 대입해도 결과는 짝수이며, 이는 한눈에 알 수 있다. 나누어떨어짐은 다음과 같이 세로선으로 나타낸다.

$$2\mid 2n$$

이 표기는 식 2n이 2로 나누어떨어진다는 뜻이다. 나누어떨어짐을 기호로 쓸 수 있으니, 수학적 귀납법으로 증명할 주장도 쓸 수 있다.

$$2\mid 2n+2;n\in \mathbb{N}$$

첫 번째 예제에서는 이것, 즉 2n + 2가 2로 나누어떨어진다는 것을 증명해야 한다. 이는 원래 문장 “어떤 짝수에 2를 더해도 다시 짝수가 된다”를 그대로 나타낸 것이다.

귀납법의 첫 단계에서는 첫 번째 원소, 즉 1에 대해 증명한다. 식에 n = 1을 대입한다.

$$\begin{array}{rcl}2& \mid & 2\cdot 1+2\\ 2& \mid & 4\end{array}$$

4는 2로 나누어떨어지므로 첫 번째 원소에 대해 성립한다. 다음은 귀납 단계로, a번째 원소에 대해 성립하면 (a + 1)번째 원소에 대해서도 성립함을 증명해야 한다. 먼저 n = a일 때 성립한다고 가정한다.

$$2\mid 2a+2$$

이 식은 참이라고 가정하고, 증명을 세울 때 이용한다. 이제 다음을 증명하려고 한다.

$$2\mid 2(a+1)+2.$$

무엇을 했을까? a 자리에 (a + 1)을 썼다. 괄호가 중요하다. 2a + 1 + 2라고 쓰면 틀린다. 식 전체에 1을 더하는 것이 아니라, a를 1만큼 큰 (a + 1)로 바꾸는 것이다. 괄호를 풀어 식을 정리한다.

$$\begin{array}{rcl}2& \mid & 2(a+1)+2\\ 2& \mid & 2a+2+2\end{array}$$

여기서 나누어떨어짐에 관해 잠깐 짚고 넘어가자. 두 수, 예를 들어 p와 q가 어떤 수, 예를 들어 r로 나누어떨어지면 그 합도 r로 나누어떨어진다. 즉 다음이 성립한다.

$$(r\mid p\wedge r\mid q)\Rightarrow r\mid (p+q)$$

예를 들어 p = 8, q = 20, r = 4를 대입해 보자. 8과 20은 모두 4로 나누어떨어진다. 그 합 8 + 20 = 28도 4로 나누어떨어진다.

이것을 예제에 어떻게 이용할까? 우변을 다음과 같이 두 수 p와 q로 나눈다.

$$p=2a+2;q=2$$

수 q, 즉 2는 당연히 2로 나누어떨어진다. 식 p도 2로 나누어떨어지는데, 가정이 그렇게 말해 주기 때문이다. 식 p는 참이라고 가정한 귀납 가정과 똑같다. p가 2로 나누어떨어지고 q도 2로 나누어떨어지므로, 그 합도 2로 나누어떨어진다.

가정에 대해 한 번 더 짚어 보자. 처음에 다음이 성립한다고 가정했다.

$$2\mid 2a+2.$$

그래서 증명을 세우는 도중에 식 2a + 2가 나왔을 때 이것이 2로 나누어떨어진다고 말할 수 있었다. 그것이 가정이기 때문이다. 귀납 가정을 언제, 왜 쓸 수 있는지 이해하는 것이 보통 수학적 귀납법에서 가장 어려운 단계이다.

이것으로 귀납법이 끝나고, 증명이 완성되어 정리가 성립한다.

원한다면 가정을 쓰지 않고 다르게 나눌 수도 있다. p = 2n, q = 2 + 2로 놓는다. q = 4는 당연히 2로 나누어떨어지고, p = 2n도 2로 나누면 자연수, 즉 정수인 n이 남으므로 2로 나누어떨어진다. 이번에도 2로 나누어떨어지는 두 식을 얻었으므로 그 합도 2로 나누어떨어진다.

어느 쪽이든 다음 두 가지를 증명했다.

1. 주어진 식은 n = 1일 때 성립한다.
2. 식이 n일 때 성립하면 n + 1일 때도 성립한다.

여기서 다음을 이끌어 낼 수 있다.

• 식은 n = 1일 때 성립한다.
• n일 때 성립하면 n + 1, 즉 1 + 1일 때도 성립해야 하므로 식은 n = 2일 때도 성립한다.
• n일 때 성립하면 n + 1, 즉 2 + 1일 때도 성립해야 하므로 식은 n = 3일 때도 성립한다.
• n일 때 성립하면 n + 1, 즉 3 + 1일 때도 성립해야 하므로 식은 n = 4일 때도 성립한다.
• n일 때 성립하면 n + 1, 즉 4 + 1일 때도 성립해야 하므로 식은 n = 5일 때도 성립한다.
• …

두 번째 예제

다음으로 간단한 주장을 수학적 귀납법으로 증명하자.

$$2^n\ge 2n;n\in \mathbb{N}.$$

먼저 첫 단계로, n을 고르는 자연수의 첫 번째 원소인 n = 1일 때 주장이 성립하는지 확인한다.

$$\begin{array}{rcl}{2}^1& \ge & 2\cdot 1\\ 2& \ge & 2\end{array}$$

이 부등식은 자명하게 성립한다. 이제 귀납 단계로 넘어가, n = a일 때 성립하면 n = a + 1일 때도 성립하는지 확인해야 한다. 가정은 다음과 같다.

$$2^a\ge 2a$$

증명하려는 식은 다음과 같다.

$$2^{a+1}\ge 2(a+1)$$

먼저 거듭제곱의 계산 법칙으로 좌변을 풀어 쓰고, 우변은 간단히 괄호를 푼다.

$$2\cdot 2^a\ge 2a+2$$

좌변에서는 곱셈 대신 덧셈을 쓰고, 우변은 그대로 둔다.

$$2^a+2^a\ge 2a+2$$

이제 가정을 이용한다. 가정은 성립한다고 가정한 명제이다. 부등식의 양변에는 각각 두 항의 합이 있다. 그런데 다음을 알고 있다.

$$\begin{array}{rcl}{2}^a& \ge & 2a\\ 2^a& \ge & 2.\end{array}$$

첫 번째 줄은 가정에서 나오고, 두 번째 줄은 자명하다(2^a은 a = 1일 때 가장 작고, 그 값은 2이다). 따라서 좌변의 두 항은 각각 우변의 두 항보다 크거나 같다. 이것으로 식이 a일 때 성립하면 (a + 1)일 때도 성립함을 귀납법으로 증명했고, 식은 1일 때도 성립하므로 주어진 식은 참이다.

세 번째 예제

다음 주장을 증명해 보자.

$$3\mid n\Rightarrow 3\mid n^2;n\in \mathbb{N}$$

말로 하면, n이 3으로 나누어떨어지면 n²도 3으로 나누어떨어진다는 뜻이다. n이 3으로 나누어떨어지지 않으면 (조건문의 정의에 따라) 식은 자명하게 성립하므로, n이 3으로 나누어떨어지는 경우만 생각하면 된다. 이런 수는 자연수의 수열 a_i=3, 6, 9, 12, 15…를 이룬다. 이제부터는 이 수열 a_i 안에서만 생각한다.

귀납법에 의한 증명은 첫 단계, 즉 첫 번째 원소에 대해 성립하는지 확인하는 것으로 시작한다. 지금은 수열 a_i 안에서 생각하고 있으므로 이 수열의 첫 번째 원소, 즉 3인 a₁을 택한다. 3에 대해서는 식이 성립한다.

$$3\mid 3\Rightarrow 3\mid 3^2$$

이제 귀납 단계로 넘어간다. 수열 a_i는 3n(n은 자연수)으로 쓸 수 있다. 즉 각 원소는 앞의 원소보다 3만큼 크다. 이제 식이 n일 때 성립한다고 가정하고, (n + 3)일 때도 성립함을 보여야 한다. 이 식은 지금 다루는 수열의 다음 원소를 만드는 규칙이다. 먼저 가정을 쓴다.

$$3\mid n\Rightarrow 3\mid n^2$$

그다음 증명하려는 것을 쓴다.

$$3\mid (n+3)\Rightarrow 3\mid (n+3{)}^2.$$

오른쪽의 괄호를 공식으로 전개한다.

$$3\mid (n+3)\Rightarrow 3\mid n^2+6n+9.$$

거의 다 왔다. 왼쪽의 식은 분명히 3으로 나누어떨어진다. 가정에 따라 n이 3으로 나누어떨어지고(수열 a_i의 수만 다루고 있다), 3도 3으로 나누어떨어지기 때문이다. 오른쪽에는 먼저 n²이 있는데, 가정에 따라 3으로 나누어떨어진다. n이 3으로 나누어떨어진다는 것을 알고, 가정은 n이 3으로 나누어떨어지면 n²도 3으로 나누어떨어진다고 말하기 때문이다.

$$3\mid n\Rightarrow 3\mid n^2$$

그다음 항 6n은 자명하게 3으로 나누어떨어진다. 분수의 약분으로 생각하면 된다.

$$\frac{6n}{3}=2n$$

n은 어떤 자연수이므로 곱 2n도 자연수이다. 즉 3으로 나누어 자연수를 얻었으므로 6n은 3으로 나누어떨어진다. 마지막의 9도 3으로 나누어떨어진다. 식이 첫 번째 원소에 대해서도, 귀납 단계에서도 성립하므로 참이다.

식 속 괄호의 개수

마지막 예제는 조금 특이하다. 단순한 식에 들어 있는 괄호의 개수는 항상 짝수라는 주장을 증명해 보자. 수학적 귀납법을 자연수만이 아니라 전혀 다른 맥락에서도 쓸 수 있음을 보여 주는 예이다. 먼저 단순한 식이 무엇인지 정의해야 한다. 단순한 식은 다음과 같다.

• 자연수,
• p가 단순한 식이면 (p²)도 단순한 식이다,
• p와 q가 단순한 식이면 (p + q)도 단순한 식이다.

예를 들어 12, 54, (5 + 6), (12 + 7), (6²), ((5 + 6)²)은 단순한 식이다. 반면 다음은 단순한 식이 아니다.

• 1 + 2 → 바깥 괄호가 없다,
• (1 + 2 → 오른쪽 괄호가 없다,
• 13² → 바깥 괄호가 없다,
• (1 + 2 + 3) → 괄호가 모자란다. 올바르게 쓰면 (1 + (2 + 3))이다.

단순한 식은 예를 들어 다음과 같이 만들 수 있다. 먼저 단순한 식 (a + b)를 고른다. 이제 a에 단순한 식 a = (c + d)를 대입하면 ((c + d) + b)를 얻고, b에 3을 대입하면 ((c + d) + 3)을 얻는다. c에 10을 대입하면 ((10 + d) + 3)이 되고, 마지막으로 d에 (5²)을 대입하면 ((10 + (5²)) + 3)이 된다. 괄호를 꼭 지켜야 한다. 그렇지 않으면 성립하지 않는다.

이제 단순한 식에는 괄호가 짝수 개 들어 있음을 증명하자(0도 짝수이다).

귀납법의 첫 단계에서는 첫 번째 원소를 고른다. 이 경우 첫 번째 원소는 가장 단순한 단순한 식, 즉 임의의 자연수이다. 따라서 다음과 같이 놓는다.

$$j=n;n\in \mathbb{N}.$$

식 j에는 괄호가 0개이므로 첫 번째 원소는 조건을 만족한다. 귀납 단계에서는 두 단순한 식 p와 q가 있고, 둘 다 괄호가 짝수 개라고 가정한다. 그러면 단순한 식 (p + q)와 (p²)에도 괄호가 짝수 개 있음을 증명해야 한다.

먼저 덧셈부터 보자. 식 q의 괄호 개수를 돌려주는 함수 z(q)를 정의한다. 그러면 식 (p + q)에는 괄호가 z(p) + z(q) + 2개 있다. 즉 식 p와 q의 괄호 수를 더한 것보다 2개 많다. 가정에 따라 z(p)와 z(q)는 모두 짝수이므로, 세 짝수를 더하면 다시 짝수가 된다. 이 경우 명제는 성립한다.

이제 거듭제곱을 보자. 이번에도 단순한 식 p에 괄호가 짝수 개 있다고 가정한다. 그러면 식 (p²)에는 괄호가 z(p) + 2개 있다. 즉 이번에도 식 p보다 괄호가 2개 많다. 이 경우에도 짝수끼리 더하므로 결과는 짝수이다.

명제가 첫 번째 원소에 대해 성립하고 귀납 단계에서도 성립하므로, 명제는 참이다.