Mathematical   Induction

이산수학 : Richard Johnsonbaugh 저서, 강홍식.김정인.이도훈.이명재 번역, 교보문고, 1999 (원서 : Discrete Mathematics 6th ed, Prentice-Hall, 1997), Page 50~56

(무한히) 긴 테이블에 1, 2, ... 의 번호가 매겨진 블록들이 놓여 있으며 일부의 블록에는 "X" 라는 글씨가 찍혀 있다고 하자 (그림 1). (그림 1 에서는 모든 블록에 X 가 찍혀 있다.) 다음과 같이 가정해 보자.

그림 1  테이블 위의 번호가 매겨진 블록들

첫 번째 블록에 마크가 찍힌다.                                                   (1)

만약 (n+1) 번째 블록보다 선행의 모든 블록에 마크가 찍혀 있다면

(n+1) 번째 블록 역시 마크가 찍힌다.                                           (2)

(1) 과 (2) 에서 모든 블록은 하나씩의 블록 검사에 의해 마크가 찍혀 있다는 의미를 포함한다. 문장 (1) 은 블록 1 이 마크된 명백한 상태이다. 블록 2 에 대해서 생각해 보자. 블록 2 보다 선행하는 모든 블록, 즉 블록 1 은 마크되어 있으므로 (2) 에 따라서 블록 2 또한 마크가 찍힌다. 블록 3 을 고려해 보자. 블록 3 보다 선행하는 모든 블록, 즉 블록 1 과 블록 2 에 마크가 찍혀 있으므로 (2) 에 의해 블록 3 역시 마크가 찍힌다. 이런 식으로 우리는 모든 블록이 마크가 찍혀 있음을 보일 수 있다. 예를 들어, 그림 1 과 같이 블록 1 에서 블록 5 까지 모두 마크가 찍혀 있는 것이 확인되었다고 하자. 그러면 그림 1 에는 보이지 않지만 블록 6 보다 선행하는 모든 블록이 마크가 찍혀 있는 것을 알고 있으므로 (2) 에 의해 블록 6 역시 마크가 찍혔다.

앞의 예는 수학적 귀납법의 원리 (Principle of Mathematical Induction) 를 설명한다. 수학적 귀납법이 어떻게 쓰여지는지 조금 더 살펴보기 위해 을 양수 1 부터 n 까지의 합이라 두자.

                                                         (3)

어떤 사람이 다음과 같이 주장했다고 가정하자.

             for                                        (4)

실지로 일련의 문장으로 나열해 보면, 즉

각 등식이 참인 경우는 옆에 '×' 표시를 한다고 하자 (그림 2). 첫 번째 등식은 모든 등식이 마크되었으면 번째의 특별한 등식보다 선행하는 모든 등식이 마크되었으면 번째의 등식 또한 마크된다고 가정해 보자. 그러면 블록들이 포함된 위의 예처럼 모든 등식들은 마크되며 모든 등식들은 참이고 따라서 식 (4) 가 성립된다.

그림 2  문장들의 수열. (참인 문장은 × 마크가 되어 있다.)

우리는 번째 등식보다 선행하는 모든 등식이 참이면 번째 등식 또한 참임을 보여야 한다. 번째 등식보다 선행하는 모든 등식이 참이라면 번째 등식은 참이다.

                                                                        (5)

번째 등식

가 참임을 밝혀야 한다. 정의 (3) 에 따라서

                                                                         (6)

이다.

그러므로 (5) 와 (6) 에 의해

이 된다.

우리의 증명은 두 단계로 구성된 수학적 귀납법을 이용하였다. 첫 번째는 일 때 그 문장이 참이라는 것을 보였다. 두 번째로 번째의 문장을 참이라고 보았을 때 번째 문장 또한 참이라는 것을 증명하였다. 번째 문장의 증명에 있어서 번째 문장의 사용을 인정한 것이며, 참으로 수학적 귀납법을 이용한 증명 비결은 번째의 문장들을 번째 문장과 관련시키는 것이다.

다음에 수학적 귀납법의 원리를 형식화된 문장으로 소개한다.

수학적 귀납법의 원리 (Principle of Mathematical Induction)

개의 양의 정수에 대하여 문장 이 존재하는데 이는 참 아니면 거짓이라 하자. 다음과 같이 가정하면

이 참이다.                                                                       (7)

만약 가 참이면 모든 에 대하여 은 참이다.        (8)

모든 양의 정수 에 대하여 은 참이다.

때때로 조건 (7) 을 기본 단계 (Basis Step) 라 하고, 조건 (8) 은 귀납단계 (Inductive Step) 라 한다. 이후부터 "귀납" 은 "수학적 귀납" 을 의미한다.

여기서 다른 예를 가지고 수학적 귀납법의 원리를 설명해 보자.

 (예제 1)

귀납법을 사용하여 다음을 보여라.

    for                                                         (9)

ㆍ기본 단계 (Basis Step) : [조건 (7)] 일 때 (9) 가 참임을 보여야 한다. 이것은 단순히 로서 기정 사실이다.

ㆍ귀납 단계 (Inductive Step) : [조건 (8)] 에 대하여 만약 이면

                                                                           (10)

임을 보여야 한다.

에 대하여 라고 가정하자. 그러면 특별한 에 대하여

                                                                               (11)

가 된다.

관찰에 의해서 (10) 과 (11) 의 관계는



로부터


                        (11) 에 의해서
                              이므로
           

가 된다.

그러므로 (10) 은 참이다. 이로서 귀납 단계를 다 살펴보았다.

기초 단계와 귀납 단계가 검증되었으며 수학적 귀납법의 원리는 모든 양의 정수 에 대하여 (9) 가 참임을 말해 준다.

귀납 단계 (8) 을 검증하기 위하여 모든 에 대하여 가 참이라 가정하여 이 참임을 증명하였다. 이와 같은 수학적 귀납법의 수식을 강성 수학적 귀납법 (strong form mathematical induction) 이라 부른다. 가끔 앞서 소개한 예제와 같이 오직 을 추정하여 을 유도할 수 있다. 사실상 귀납 단계는 가끔 다음과 같은 상태가 된다.

만약 이 참이면 은 참이다.

이들 두 식에서 기초 단계는 바뀌지 않았다. 다만 수학적 귀납법의 두 가지 양식이 논리적으로 동치임을 보였다.

만약 일 때 다음 문장이 참임을 검증하고 싶다면

기본 단계에서

가 참이어야 한다.

귀납 단계는 변하지 않는다.

 (예제 2)  기하학적 합

에 대하여 일 때 귀납법을 사용하여 다음을 보여라.

                                        (12)

좌변의 합을 기하학적 합 (geometric sum) 이라 한다. 기하학적 합에서 연속적인 항들 () 의 비율은 일정하다.

ㆍ기본 단계 :  을 대입하면 다음을 얻을 수 있으며



이는 참이다.

ㆍ귀납 단계 :  에 대하여 (12) 가 참이라 가정하면



이 된다. 기초 단계를 수정하여 귀납 단계를 검증하였으며, 수학적 귀납법의 원리는 에 대하여 (12) 가 참임을 말해 준다.

기하학적 합을 이용하는 예제처럼 (12) 에서 로 놓으면 다음 식을 얻을 수 있다.

앞의 식을 증명하기에 앞서서 하나의 옳은 식이 주어져야 한다는 것이 확실히 알려졌다. 여기서 적절한 질문은 어떻게 하나의 식을 뽑을 수 있는 가이다. 이 질문에는 많은 대답이 있다. 식을 유도하는 기술의 하나는 경험에 의해 작은 값으로 시도하여 패턴을 찾아내는 것이다. 예를 들면, 의 합을 생각해 보자. 에 대한 합의 값을 갖는 테이블은 다음과 같다.

제곱들로 구성된 두 번째 열로부터 모든 양의 정수 에 대하여

임을 어림짐작으로 알 수 있다.

이 짐작은 옳으며 식은 수학적 귀납법 (연습 문제 1) 에 의해 증명될 수 있다. 마지막 두 개의 예제는 합계들에 대한 식과 부등식들을 증명하기에 귀납법은 제한이 없음을 보여 준다.

 (예제 3)  

에 대하여 귀납법을 이용하여   이 4 로 나누어짐을 보여라.

ㆍ기본 단계 : 만약 이면 이며 4 로 나누어진다.

ㆍ귀납 단계 :  이 4 로 나누어진다고 가정하자. 이 4 로 나누어짐을 보여야 한다. 번째와 번째의 관계에서



로 적을 수 있다. 가정에 의해서 은 4 로 나누어지며, 그리고 도 4 로 나누어지므로 합계

는 4 로 나누어진다. 기초 단계와 귀납 단계가 검증되었으므로, 일 때 수학적 귀납법의 원리는 우리에게 은 4 로 나누어진다고 말할 수 있다.

 (예제 4)   타일 문제

우 트로미노 (right tromino : 앞으로는 단순히 트로미노로 부르겠다) 는 그림 3 과 같이 3 개의 정사각형으로 구성된 물체이다. 트로미노는 포리오미노의 한 형태이다. 포리오미노는 1954년 Solomon W.Golomb 에 의해 소개되었으며 ([Golomb, 1954] 참조), 그들은 오락 수학에 즐겨 사용하였다. 포리오미노의 차수는 가장자리가 겹치는 정사각형으로 구성된다. 트로미노는 3 차 포리오미노이다. 3 개의 사각형이 행으로 놓인 것은 차수 3 인 포리오미노의 한 가지 다른 형태일 뿐이다. 포리오미노를 이용하여 수많은 문제들이 연구되었는데 ([Martin] 참조), 그 중 Golomb 의 귀납적 증명을 살펴보자.

그림 3  트로미노

만약 보드에서 하나의 사각형을 제거하면 ( 은 2 의 멱승), 오른쪽의 트로미노들로 남은 부분을 덮을 수 있다 (그림 4). 트로미노들의 타일모양에 의해 각각의 트로미노들이 겹치지 않으며 그림의 바깥 부분이 늘어나지 않도록 배치하여 정확히 덮는다. 하나의 사각형이 빠진 보드를 불완전 보드 (deficient board) 라 한다.

그림 4  트로미노들로 덮은 불완전 보드

에 의한 귀납법을 이용하여 의 트로미노들로 구성된 불완전 보드를 증명할 수 있다.

ㆍ기본 단계 : 만약 이면 의 불완전 보드는 트로미노 자신이며, 하나의 트로미노에 의해 덮일 수 있다.

ㆍ귀납 단계 : 의 불완전 보드를 타일로 덮을 수 있다고 가정하자. 우리는 불완전 보드를 덮을 수 있다는 것을 보여야 한다.

불완전 보드를 생각해 보자. 그림 5 에서 보여 주는 것처럼 4 개의 보드로 나눌 수 있다. 빠진 사각형이 네 부분 중에서 왼쪽 윗 부분에 가도록 보드를 돌린다. 귀납적 가정에 의해서 왼쪽 윗 부분 보드는 타일로 덮여진다. 그림 5 에서 가운데 부분의 한 트로미노는 각 사각형이 다른 사분면에 위치한다. 만약 T 에 의해서 사각형들이 덮여진다면 각 사분면은 불완전 보드가 된다. 다시 말하면, 귀납적 가정에 의해 이 보드들은 타일로 덮여진다. 우리는 지금 보드에서 타일을 덮고 있다. 수학적 귀납법의 원리에 의해 일 때 어떤    불완전 보드도 트로미노들에 의해 타일로 덮여진다.

T

그림 5  수학적 귀납법을 이용하여 트로미노들로 덮은  불완전 보드

만약 불완전 보드를 타일로 덮을 수 있다면 사각형들의 수 은 반드시 3 으로 나누어진다 ( 이 2 의 멱승일 필요는 없다). [Chu] 는 일 때를 제외하고 그 역이 참이라는 것을 보였다. 보다 정확하게, 만약 이면 어떤 불완전 보드도 3 에 의해 나누어지는 의 트로미노들에 의해 타일로 덮여진다. [일부 불완전 보드들은 타일로 덮여지며 다른 일부는 그렇지 않다 (연습 문제 32, 33 을 보라)].