04. 수열의 귀납적 정의 02

흰 돌과 검은 바둑돌로 다음 그림과 같은 칸에 채우려고 한다. 이 때, 검은 바둑돌끼리는 이웃하지 않게 칸을 채운다고 할 때, 11개의 칸을 채우는 방법은 모두 몇 가지인가? (단, 첫째 칸에 오는 바둑돌의 색은 어떤 것이어도 상관없다고 한다.)

• 수열은 규칙이다.
• 규칙 : 검은 바둑돌끼리 이웃하지 않게 나열한다.

• 사건들을 나열한 후 수열의 귀납적 정의로 표현하자.

편의상 검은 바둑돌은 $B$$~B$, 흰 바둑돌은 $W$$~W$을 이용하여 적어보자. 단, 항끼리의 연관관계를 쉽게 찾을 수 있도록 규칙을 이용해서 표현하자.

$\begin{array}{cccccccccccccc}{a}_1& & & & & W& & & b_1& & & & & B\\ a_2& & & & W& W& & & b_2& & & & W& B\\ & & & & B& W& & & & & & & & \\ a_3& & & W& W& W& & & b_3& & & W& W& B\\ & & & B& W& W& & & & & & B& W& B\\ & & & W& B& W& & & & & & & & \\ a_4& & W& W& W& W& & & b_4& & W& W& W& B\\ & & B& W& W& W& & & & & B& W& W& B\\ & & W& B& W& W& & & & & W& B& W& B\\ & & W& W& B& W& & & & & & & & \\ & & B& W& B& W& & & & & & & & \end{array}$$\begin{matrix} a_{ 1 } & & & & & W & & & b_{ 1 } & & & & & B \\\ a_{ 2 } & & & & W & W & & & b_{ 2 } & & & & W & B \\\ & & & & B & W & & & & & & & & \\\ a_{ 3 } & & & W & W & W & & & b_{ 3 } & & & W & W & B \\\ & & & B & W & W & & & & & & B & W & B \\\ & & & W & B & W & & & & & & & & \\\ a_{ 4 } & & W & W & W & W & & & b_{ 4 } & & W & W & W & B \\\ & & B & W & W & W & & & & & B & W & W & B \\\ & & W & B & W & W & & & & & W & B & W & B \\\ & & W & W & B & W & & & & & & & & \\\ & & B & W & B & W & & & & & & & & \end{matrix}$

조금 보기 편하게 역시 선을 그어보자.

$\begin{array}{cccccccccccccc}{a}_1& & & & & W& & & b_1& & & & & B\\ a_2& & & & W& W& & & b_2& & & & W& B\\ & & & & B& W& & & & & & & & \\ a_3& & & W& W& W& & & b_3& & & W& W& B\\ & & & B& W& W& & & & & & B& W& B\\ & & & W& B& W& & & & & & & & \\ a_4& & W& W& W& W& & & b_4& & W& W& W& B\\ & & B& W& W& W& & & & & B& W& W& B\\ & & W& B& W& W& & & & & W& B& W& B\\ & & W& W& B& W& & & & & & & & \\ & & B& W& B& W& & & & & & & & \end{array}$$\begin{array}{ccccc|cccccccc|c} a_{ 1 } & & & & & W & & & b_{ 1 } & & & & & B \\\ a_{ 2 } & & & & W & W & & & b_{ 2 } & & & & W & B \\\ & & & & B & W & & & & & & & & \\\ a_{ 3 } & & & W & W & W & & & b_{ 3 } & & & W & W & B \\\ & & & B & W & W & & & & & & B & W & B \\\ & & & W & B & W & & & & & & & & \\\ a_{ 4 } & & W & W & W & W & & & b_{ 4 } & & W & W & W & B \\\ & & B & W & W & W & & & & & B & W & W & B \\\ & & W & B & W & W & & & & & W & B & W & B \\\ & & W & W & B & W & & & & & & & & \\\ & & B & W & B & W & & & & & & & & \end{array}$

자! 숨은 그림 찾기!

$\begin{array}{cccccccccccccc}{a}_1& & & & & W& & & b_1& & & & & B\\ a_2& & & & W& W& & & b_2& & & & W& B\\ & & & & B& W& & & & & & & & \\ a_3& & & W& W& W& & & b_3& & & W& W& B\\ & & & B& W& W& & & & & & B& W& B\\ & & & W& B& W& & & & & & & & \\ a_4& & W& W& W& W& & & b_4& & W& W& W& B\\ & & B& W& W& W& & & & & B& W& W& B\\ & & W& B& W& W& & & & & W& B& W& B\\ & & W& W& B& W& & & & & & & & \\ & & B& W& B& W& & & & & & & & \end{array}$$\begin{array}{ccccc|cccccccc|c} a_{ 1 } & & & & & \color{red}{W} & & & b_{ 1 } & & & & & B \\\ a_{ 2 } & & & & \color{lime}{W} & \color{lime}{W} & & & b_{ 2 } & & & & \color{red}{W} & B \\\ & & & & \color{lime}{B} & \color{lime}{W} & & & & & & & & \\\ a_{ 3 } & & & \color{fuchsia}{W} & \color{fuchsia}{W} & \color{fuchsia}{W} & & & b_{ 3 } & & & \color{lime}{W} & \color{lime}{W} & B \\\ & & & \color{fuchsia}{B} & \color{fuchsia}{W} & \color{fuchsia}{W} & & & & & & \color{lime}{B} & \color{lime}{W} & B \\\ & & & \color{fuchsia}{W} & \color{fuchsia}{B} & \color{fuchsia}{W} & & & & & & & & \\\ a_{ 4 } & & W & W & W & W & & & b_{ 4 } & & \color{fuchsia}{W} & \color{fuchsia}{W} & \color{fuchsia}{W} & B \\\ & & B & W & W & W & & & & & \color{fuchsia}{B} & \color{fuchsia}{W} & \color{fuchsia}{W} & B \\\ & & W & B & W & W & & & & & \color{fuchsia}{W} & \color{fuchsia}{B} & \color{fuchsia}{W} & B \\\ & & W & W & B & W & & & & & & & & \\\ & & B & W & B & W & & & & & & & & \end{array}$

위의 표를 보고 우리는 $b_n$$b_n$을 유추할 수 있다. $b_n$$~b_n$은 경우의 수임을 기억하자.

$\begin{array}{rl}{b}_2& =a_1\\ b_3& =a_2\\ b_4& =a_3\\ & ⋮\\ b_n& =a_{n-1}\\ b_{n+1}& =a_n\end{array}$$\begin{align} b_2 &=a_1 \\\ b_3 &=a_2 \\\ b_4&=a_3 \\\ &\vdots \\\ b_n &=a_{n-1} \\\ b_{n+1}&=a_n\end{align}$

이제, $a_n$$~a_n$의 점화식에 대해 찾아보면,

$\begin{array}{cccccccccccccc}{a}_1& & & & & W& & & b_1& & & & & B\\ a_2& & & & W& W& & & b_2& & & & W& B\\ & & & & B& W& & & & & & & & \\ a_3& & & W& W& W& & & b_3& & & W& W& B\\ & & & B& W& W& & & & & & B& W& B\\ & & & W& B& W& & & & & & & & \\ a_4& & W& W& W& W& & & b_4& & W& W& W& B\\ & & B& W& W& W& & & & & B& W& W& B\\ & & W& B& W& W& & & & & W& B& W& B\\ & & W& W& B& W& & & & & & & & \\ & & B& W& B& W& & & & & & & & \end{array}$$\begin{array}{ccccc|cccccccc|c} a_{ 1 } & & & & & W & & & b_{ 1 } & & & & & B \\\ a_{ 2 } & & & & W & W & & & b_{ 2 } & & & & W & B \\\ & & & & B & W & & & & & & & & \\\ a_{ 3 } & & & \color{red}{W} & \color{red}{W} & \color{red}{W} & & & b_{ 3 } & & & \color{blue}{W} & \color{blue}{W} & \color{blue}{B} \\\ & & & \color{red}{B} & \color{red}{W} & \color{red}{W} & & & & & & \color{blue}{B} & \color{blue}{W} & \color{blue}{B} \\\ & & & \color{red}{W} & \color{red}{B} & \color{red}{W} & & & & & & & & \\\ a_{ 4 } & & \color{red}{W} & \color{red}{W} & \color{red}{W} & W & & & b_{ 4 } & & W & W & W & B \\\ & & \color{red}{B} & \color{red}{W} & \color{red}{W} & W & & & & & B & W & W & B \\\ & & \color{red}{W} & \color{red}{B} & \color{red}{W} & W & & & & & W & B & W & B \\\ & & \color{blue}{W} & \color{blue}{W} & \color{blue}{B} & W & & & & & & & & \\\ & & \color{blue}{B} & \color{blue}{W} & \color{blue}{B} & W & & & & & & & & \end{array}$

위의 색깔별로 포함된 관계를 이용해서 수열 $a_n$$~a_n$을 유추해 보면,

$\begin{array}{rl}{a}_2& =a_1+b_1\\ a_3& =a_2+b_2\\ a_4& =a_3+b_3\\ & ⋮\\ a_n& =a_{n-1}+b_{n-1}\\ a_{n+1}& =a_n+b_n\end{array}$$\begin{align} a_2 &=a_1+b_1 \\\ a_3 &= a_2 +b_2\\\ a_4&=a_3 +b_3 \\\ &\vdots \\\ a_n &=a_{n-1}+b_{n-1}\\\ a_{n+1}&=a_n+b_n\end{align}$

이제 구한 점화식을 정리하면,

$\begin{array}{c}\{\begin{array}{rl}{a}_{n+1}& =a_n+b_n\\ b_{n+1}& =a_n\end{array}\end{array}$$\left\{ \begin{align}a_{n+1} &=a_n+b_n \\\ b_{n+1}&=a_n\end{align}\right.$

점화식을 보고 설명하기

위에서 정의한 수열의 정의를 보면,

$a_n:n$$a_n~:~n$번째 바둑칸에 흰 바둑돌이 오는 경우의 수

$b_n:n$$b_n~:~n$번째 바둑칸에 검은 바둑돌이 오는 경우의 수

이를 기본으로 점화식을 설명하면,

$a_{n+1}=a_n+b_n$$a_{n+1} =a_n+b_n$

$(n+1)$$(n+1)$번째 칸에 흰 바둑돌이 오는 경우의 수는 $n$$~n$번째 칸에 흰 바둑돌이 오는 경우와 검은 바둑돌이 오는 경우의 수의 합이다.

$b_{n+1}=a_n$$b_{n+1}=a_n$

$(n+1)$$(n+1)$번째 칸에 검은 바둑돌이 오는 경우의 수는 $n$$~n$번째 칸에 흰 바둑돌이 오는 경우의 수와 같다. (검은 바둑돌은 이웃하게 놓지 않는다.)

이제 훈련이 되었다면, 간단하게 문제를 풀도록 하자.

수열의 귀납정 정의를 이용하기

$a_n:n$$a_n~:~n$번째 바둑칸에 흰 바둑돌이 오는 경우의 수

$b_n:n$$b_n~:~n$번째 바둑칸에 검은 바둑돌이 오는 경우의 수

위의 수열의 정의대로 점화식을 세워보면,

$\begin{array}{cc}(n+1)\text{번째}& n\text{번째}\\ \underset{a_{n+1}}{W}& \leftarrow \underset{a_n}{W}\\ & \nwarrow \underset{b_n}{B}\end{array}$$\begin{array}{c|c} (n+1)\text{번째}~~ & n\text{번째}~~ \\\ \large \underset{a_{n+1}}{W} & \large \leftarrow \underset{a_n}{W} \\\ & \large \nwarrow\underset{b_n}{B}\end{array}$

표를 보듯이 $(n+1)$$~(n+1)$번 째에 흰 바둑돌이 오는 경우는 $n$$~n$번째에 흰 바둑돌을 놓은 경우에 흰 바둑돌을 두는 경우와 검은 바둑돌을 놓은 경우에 흰 바둑돌을 놓는 경우의 수의 합이다.

$\therefore a_{n+1}=a_n+b_n$$\therefore~ a_{n+1}=a_n+b_n$

$\begin{array}{cc}(n+1)\text{번째}& n\text{번째}\\ \underset{b_{n+1}}{B}& \leftarrow \underset{a_n}{W}\end{array}$$\begin{array}{c|c} (n+1)\text{번째}~~ & n\text{번째}~~ \\\ \large \underset{b_{n+1}}{B} & \large \leftarrow \underset{a_n}{W} \end{array}$

역시, $(n+1)$$~(n+1)$번째 칸에 검은 바둑돌을 놓은 경우는 $n$$~n$번째에 흰 바둑돌을 놓은 경우에 검은 바둑돌을 놓는 경우이므로 $(n+1)$$~(n+1)$번째에 검은 바둑돌을 놓는 경우의 수는 $n$$~n$번째에 흰 바둑돌을 놓는 경우의 수와 같다.

$\therefore b_{n+1}=a_n$$\therefore~ b_{n+1}=a_n$

이 점화식을 구하는 것은 문제를 풀기위한 과정에 지나지 않는다. 최종적으로 $n+1$$n+1$회 째에 검은 돌이 연속하지 않도록 바둑돌을 놓는 경우의 수를 $c_{n+1}$$c_{n+1}$이라 하면,

$\begin{array}{c}\{\begin{array}{rl}{a}_{n+1}& =a_n+b_n\\ \\ b_{n+1}& =a_n\\ \\ c_{n+1}& =a_{n+1}+b_{n+1}\end{array}\end{array}$$\left\{ \begin{align}a_{n+1} &=a_n+b_n \\\ \\\ b_{n+1}&=a_n \\\ \\\ c_{n+1}&=a_{n+1}+b_{n+1}\end{align}\right.$

그리고, $b_n=a_{n-1}$$~b_n =a_{n-1}$을 대입하면,

$a_{n+1}=a_n+a_{n-1}$$a_{n+1} =a_n +a_{n-1}$

첨자를 정리하면,

$a_{n+2}=a_{n+1}+a_n$$a_{n+2} =a_{n+1}+a_n$

이 관계를 이용하면,

$c_{n+1}=a_{n+2}=a_{n+1}+a_n$$c_{n+1} =a_{n+2} =a_{n+1} +a_n$

즉, $a_{12}$$~a_{12}$를 구하면 된다.

$a_1=1,a_2=2$$a_1 =1,~~a_2 =2$

$\begin{array}{rl}{a}_3& =a_2+a_1=2+1=3\\ a_4& =a_3+a_2=3+2=5\\ a_5& =8\\ a_6& =13\\ a_7& =21\\ a_8& =34\\ a_9& =55\\ a_{10}& =89\\ a_{11}& =144\\ a_{12}& =233\end{array}$$\begin{align} a_3 &=a_2+a_1 =2+1=3 \\\ a_4&=a_3 +a_2 =3+2=5 \\\ a_5&=8 \\\ a_6&=13 \\\ a_7 &=21 \\\ a_8&=34 \\\ a_9&=55 \\\ a_{10}&=89 \\\ a_{11}&=144 \\\ a_{12} &=233 \end{align}$

경우의 수 문제 또는 확률 문제에 활용되는 경우가 은근히 존재한다.

예를 하나 들면,

비가 온 후 다음 날 비가 올 확률이 $\frac{2}{3}$$\cfrac 23$이고, 맑은 다음 날 비가 올 확률이 $\frac{1}{3}$$\cfrac 13$일 때, 월요일 비가 왔다. 일요일에 비가 왔을 때, 토요일에 비가 왔을 확률을 구하시오.