수열의 귀납적 정의
본문가로 2, 세로 \(n\)인 판을 \(1 \times 2\) 크기의 타일로 빈틈없이 덮는 방법의 수를 \(a_n\)이라 하자. \(n = 10\)일 때의 방법은 그림을 다 그려 세기에는 너무 많다. 그런데 \(a_9\)와 \(a_8\)을 알면 \(a_{10}\)을 바로 구할 수 있다고 한다. 어떻게 그럴까?
3.6.1첫째항과 규칙으로 정하기
수열은 일반항으로 정할 수도 있지만, 첫째항과 이웃한 항 사이의 관계로 정할 수도 있다. 가령 '\(a_1 = 3\)이고, \(a_{n+1} = a_n + 2\)'라고 하면 \(a_2 = 5\), \(a_3 = 7\), …로 모든 항이 차례로 정해진다. 이렇게 처음 몇 항과 이웃한 항 사이의 관계식으로 수열을 정하는 것을 수열의 귀납적 정의라 하고, 관계식을 점화식이라 한다.
\(a_{n+1} = a_n + d\)이면 공차가 \(d\)인 등차수열이고, \(a_{n+1} = ra_n\)이면 공비가 \(r\)인 등비수열이다. \(2a_{n+1} = a_n + a_{n+2}\)이면 등차수열, \(a_{n+1}^2 = a_na_{n+2}\)이면 등비수열이다.
3.6.2경우를 나누어 점화식 세우기
점화식은 일반항을 찾기 어려운 문제에서 특히 쓸모 있다. 처음 질문의 판에서 맨 오른쪽 끝을 어떻게 덮었는지로 경우를 나누어 보자. 세로 타일 하나로 덮었다면 나머지 \(2 \times (n - 1)\) 판을 덮는 방법은 \(a_{n-1}\)가지이다. 가로 타일 두 개를 위아래로 겹쳐 덮었다면 나머지는 \(2 \times (n - 2)\) 판이고 \(a_{n-2}\)가지이다.
두 경우는 겹치지 않고 모든 경우를 빠짐없이 나누므로, 합의 법칙에 따라 \(a_n = a_{n-1} + a_{n-2}\)이다. 그런데 이 식만으로는 출발할 수 없다. \(a_1 = 1\), \(a_2 = 2\)를 직접 세어 주어야 \(a_3 = 3\), \(a_4 = 5\), \(a_5 = 8\), …이 차례로 정해진다. 그림 1의 슬라이더로 \(n\)을 바꾸어 보면 두 경우의 수가 앞의 두 값이다.1
3.6.3예제 풀이
처음 질문의 \(a_{10}\)을 구하여라. 또 \(a_1 = 1\), \(a_{n+1} = 2a_n + 1\)로 정해진 수열의 제5항을 구하고, \(b_n = a_n + 1\)로 두어 일반항을 구하여라.
\(a_1 = 1\), \(a_2 = 2\)에서 점화식으로 차례로 더하면 3, 5, 8, 13, 21, 34, 55, 89이므로 \(a_{10} = 89\)이다. 10칸짜리 판을 덮는 방법이 89가지라는 것을 그림을 하나도 그리지 않고 얻었다.
두 번째 수열은 1, 3, 7, 15, 31이므로 제5항은 31이다. 그런데 각 항에 1을 더하면 2, 4, 8, 16, 32로 등비수열처럼 보인다. 실제로 \(b_{n+1} = a_{n+1} + 1 = 2a_n + 2 = 2b_n\)이므로 \(\{b_n\}\)은 첫째항 2, 공비 2인 등비수열이다.
따라서 \(b_n = 2^n\)이고 \(a_n = 2^n - 1\)이다. 점화식을 아는 꼴로 바꾸는 치환 하나로 일반항까지 얻은 셈이다. 아래 탐구 카드에서 점화식의 첫째항과 규칙을 바꾸며 수열이 어떻게 이어지는지 직접 확인해 보자.
- \(a_n = a_{n-1} + a_{n-2}\)를 만족하는 수열 1, 1, 2, 3, 5, 8, …을 피보나치수열이라 한다. 이웃한 두 항의 비 \(\tfrac{a_{n+1}}{a_n}\)은 \(n\)이 커질수록 황금비 \(\tfrac{1 + \sqrt{5}}{2} \approx 1.618\)에 가까워진다.
귀납적 정의는 처음 몇 항과 이웃한 항 사이의 점화식으로 수열을 정하며, 일반항을 바로 찾기 어려운 경우의 수 문제에서 경우를 나누어 점화식을 세우면 쉽게 풀린다. 그래서 처음 질문의 판은 맨 끝을 덮는 두 가지 방법으로 나누어 \(a_n = a_{n-1} + a_{n-2}\)를 얻고, \(a_{10} = 89\)이다.