Induction II

수학적 귀납법이 증명을 하는데 아주 유용한 도구라는 것은 어느정도 수학을 했던 사람이라면 잘 알고 있는 사실입니다. 실제 수학적 귀납법을 익히는 것은 어렵지 않지만, 많은 분들이 수학 증명이라는 말만 나오면 일단 겁부터 내는 듯합니다.

 

수학적 귀납법은 패턴이 정해져 있는 증명으로 몇 번 하면 수학에 재능이 없다고 하는 분들도 그다지 어렵지 않게 익힐 수가 있습니다. 물론 수식 계산에 자신이 없다면 어쩔 수 없겠지만요.

 

옛날 그리스 사람인 니코마소스(Nicomachus)의 정리를 보도록 하겠습니다. 세제곱의 수가 홀수들의 합으로 표시할 수 있다는 것이죠.

 

\[ \begin{align} 1^3 &= 1 \\ 2^3 &= 3+5 \\ 3^3 &= 7+9+11 \\ 4^3 &= 13+15+17+19 \\ ... \end{align} \]

 

문제는 이것을 수학적 귀납법을 이용해서 증명하자는 것입니다.

 

제일 먼저 할 일은 참, 거짓을 가릴 수 있는 명제를 만들어야 합니다. 위의 식을 보면, 홀수가 1, 3, 5, 7, ... 형태로 한번씩만 쓰인 것을 알 수 있습니다. 이것을 식으로 표현하면 다음과 같이 표현할 수 있습니다.

 

\[ P(n) : n^3 = (n^2 - n + 1) + ... + (n^2 + n - 1) \]

 

사실 이 증명은 수학적 귀납법으로 처리하는 것보다는 등차수열의 합 공식을 이용하는 것이 더 간단합니다.

 

\[ (n^2 - n + 1) + ... + (n^2 + n - 1) = \frac{n( 2n^2 )}{2} = n^3 \]

 

귀납법으로 증명하기 위해서는 n번째 등식과 n+1번째 등식과의 상관관계를 살펴보아야 한다. 우변의 첫째항만을 비교한다면 n번째 등식보다 n+1번째 등식이 2n만큼 크다. 즉 n번째 등식의 우변보다 n+1번째 등식의 우변은 다음과 같다. n번째 등식의 우변을 R(n)이라 표현하면,

 

\[ \begin{align} R(k+1) - R(k) &= 2k \cdot k + ((k+1)^2 + (k+1) - 1) \\ &= 2k^2 + k^2 + 2k + 1 + k \\ &= 3k^2 + 3k + 1\end{align} \]

 

그러면 수학적 귀납법으로 증명하면,

 

i) n = 1

   \( 1^3 = 1 \)

ii) Assume that \( (k^2 - k + 1) + ... (k^2 + k - 1) = k^3 \)

iii) n = k+1

  \( R(k+1) = R(k) + 3k^2 + 3k + 1 = k^3 + 3k^2 + 3k + 1 = (k+1)^3 \)

 

이로써 수학적 귀납법으로 증명이 되었다.

 

사실 이 예가 수학적 귀납법을 설명하는데 좋은가라고 물어본다면, 그다지 좋은 예는 아닐 듯 하다. 크누스의 저서에 연습문제에 나온 것을 발췌했을 뿐..

 

이미 수학적 귀납법이 알고리즘에 유효성을 검사하는 도구로 사용할 수 있다고 이야기한만큼 여기서 실제 알고리즘에 적용해보도록 한다. 크누스의 저서에서는 글로 설명되어 있지만, 여기서는 C 언어 코드를 빌려서 해볼까 합니다.

 

//    Extended Euclid's algorithm
int ExtendedEuclid(int m, int n)
{
    int a, b, _a, _b, c, d, r, t;

E1: _a = b = 1; a = _b = 0; c = m; d = n;
E2: q = c/d; r = c%d;
E3: if( r == 0 )
    {
        printf("%dx%d+%dx%d=%d\n", a, m, b, n, d);
        return d;
    }
E4: c = d; d = r; t = _a; _a = a; a = t- q*a; t = _b; _b = b; b = t-q*b;
    goto E2;
}

 

이번에 적은 유클리드 알고리즘은 너무나도 복잡합니다. 사실 여기서 유클리드 알고리즘은 알고리즘 종료시 am+bn=d 라는 공식이 성립하도록 하고 있죠. 수학 쪽에서 a, b 값을 찾아야 하는 경우가 많습니다. 예를 들어서 4로 나누면 2가 남고 5로 나누면 4가 남는 수를 찾아라한다면, -1*4 + 1*5 = 1 을 이용해서 풀 수 있죠. 이러면 간단하게 -1*4*4 + 1*5*2 = -6 란 답을 낼 수 있다. 즉 20k-6 가 답이 됩니다. 이것을 중국인의 나머지 정리라 합니다.

 

이 알고리즘에서 가장 중요한 부분은 E2 라인으로 들어오는 곳에서 우리가 설정한 변수의 역할이 정확한 가이다. 실제 다른 사람들의 프로그램을 보면, 변수에 대한 정확한 정의 없이 프로그램을 시작하는 경우가 많다. 이것은 올바르지 않은 자세라고 본다.

 

여기서 입력은 m, n 이며, 출력은 a, b, d 이다. E1->E2로 가는 곳에서는 명확하다. a = 0, b = 1, d = n 이므로 am+bn=d 식을 만족한다. 그리고 _a = 1, _b = 0, c = m이므로 _am+_bn=c 도 만족한다. 그리고 gcd(m, n) = gcd(c, d) 를 만족한다.

 

E4에서 증명을 하도록 한다. E2에서 am+bn=d 와 _am+_bn=c 를 만족한다고 가정하면,

E2에서 c = qd + r 이라고 표현할 수 있다.

c ← d, t ← _a, _a ← a, a ← t-qa 에 의해서,

_am+bn=c, (a+q_a)m+_bn=qc+r 이 되고,

마찬가지로 d ← r, t ← _b, _b ← b, b ← t-qb 에 의해서

_am+_bn=c, (a+q_a)m+(b+q_b)n=qc+d 가 된다.

그런데 _am+_bn=c 이므로 두 번째 식은 am+bn=d 가 되어 처음에 설정한 식을 만족하게 된다. 마찬가지로 gcd(c, d) = gcd(d, r)이 되어 원래의 유클리드 알고리즘에 의해서 이 역시 성립한다.

 

이렇게 함으로써 E2에서 보았을 때, 세가지 항목을 모두 만족한다.

 

이제 남은 것은 이 알고리즘이 종료할 것인가이다. 0 ≤ r < d 이므로 E4를 거치게 되면 새로운 (c, d) 쌍은 이전의 (c, d) 쌍 값보다 항상 작은 값을 가지게 되므로 언젠가는 r은 0이 된다.

 

사실 저도 수학 전공자가 아니기 때문에 증명하는 방법에서 기호, 논리에 비약이 있을 수 있습니다.