수열의 귀납적 정의

폭 2, 길이 10인 복도에 1×2 크기의 직사각형 타일을 빈틈없이 깔려고 한다. 타일은 세로로 세워도 되고 가로로 눕혀도 된다. 깔 수 있는 방법을 모두 그려 보기에는 너무 많다. 그런데 복도 맨 왼쪽 끝을 어떻게 덮는지만 생각하면, 길이 10의 문제를 길이 9와 길이 8의 문제로 나눌 수 있다고 한다. 이렇게 앞의 항으로 다음 항을 정하는 방법으로 개수를 셀 수 있을까? 하노이의 탑 문제도 같은 방법으로 풀릴까?

2.1.1작은 문제로 나누다

복도의 맨 왼쪽 두 칸을 덮는 방법은 세로로 세운 타일 하나이거나, 위아래로 포갠 가로 타일 두 개이다. 가로 타일을 하나만 놓으면 그 아래 칸은 다른 가로 타일로만 덮을 수 있어 결국 두 개를 함께 놓게 된다. 세로 타일 하나로 덮으면 남은 길이 \(n - 1\)의 복도를 아무렇게나 깔면 되고, 가로 타일 두 개로 덮으면 남은 길이 \(n - 2\)의 복도를 깔면 된다. 두 경우는 겹치지 않으므로 합의 법칙으로 \(T_n = T_{n-1} + T_{n-2}\)이다. 처음 두 값 \(T_1 = 1\), \(T_2 = 2\)만 알면 모든 항이 차례로 정해진다.

하노이의 탑에서 가장 큰 원판을 옮기려면, 먼저 그 위의 원판 \(n - 1\)개를 모두 보조 기둥으로 옮겨야 한다. 그다음 큰 원판을 목표 기둥으로 한 번 옮기고, 다시 \(n - 1\)개를 그 위로 옮긴다. 그래서 \(H_n = H_{n-1} + 1 + H_{n-1} = 2H_{n-1} + 1\)이다. 양변에 1을 더하면 \(H_n + 1 = 2(H_{n-1} + 1)\)이어서 \(H_n + 1\)은 공비 2인 등비수열이고, \(H_1 + 1 = 2\)이므로 \(H_n = 2^n - 1\)이다.¹

2.1.2경우를 빠짐없이, 겹침 없이

점화 관계를 세울 때는 첫 단계를 나누는 경우가 빠짐없이 모든 경우를 덮고, 서로 겹치지 않는지 확인해야 한다. 타일 문제에서 왼쪽 끝이 세로 타일인 경우와 가로 타일 두 개인 경우는 서로 다르고, 이 밖의 경우는 없다. 만약 경우가 겹치면 한 배열을 두 번 세고, 빠지면 덜 센다. 또 처음 항을 잘못 정하면 모든 항이 틀어지므로, 작은 \(n\)에서는 직접 그려 세어 확인하는 것이 좋다.

2.1.3예제 풀이

\(T_1 = 1\), \(T_2 = 2\)에서 점화 관계로 3, 5, 8, 13, 21, 34, 55, 89가 차례로 나와 \(T_{10} = 89\)이다. 이 수열은 피보나치 수열을 한 칸 민 것이다.

길이 4의 배열을 V와 H로 적으면 VVVV, VVH, VHV, HVV, HH의 다섯 가지이다. 이 가운데 V로 시작하는 것은 VVVV, VVH, VHV의 세 가지로, 뒤의 부분이 길이 3의 배열 VVV, VH, HV와 같아 \(T_3 = 3\)이다. H로 시작하는 것은 HVV, HH의 두 가지로, 뒤의 부분이 길이 2의 배열과 같아 \(T_2 = 2\)이다. 그래서 \(T_4 = 3 + 2 = 5\)이다. 즉 큰 문제를 첫 단계의 경우로 나누어 더 작은 같은 꼴의 문제로 바꾸면, 처음 항과 점화 관계로 수열을 귀납적으로 정의해 개수를 셀 수 있다.

아래 탐구 카드에서 하노이의 탑을 직접 옮겨 최소 횟수의 규칙을 찾고, 2×\(n\) 복도에 타일을 까는 방법을 점화 관계로 세어 보자.

1. 하노이의 탑은 1883년 프랑스의 수학자 뤼카가 만든 놀이이다. 그는 인도의 사원에서 승려들이 64개의 금 원판을 옮기고 있으며, 다 옮기면 세상이 끝난다는 이야기를 함께 지어 붙였다.