1과 2로 만든 다섯 자리 수

[출제의도] 경우의 수 이해하기

$1$로 시작하는 경우의 수가 $8$가지이므로 $2$로 시작하는 경우의 수도 $8$가지이다. 따라서 $16$개이다. [별해] $1 \ne 2 = 2 \ne 1 = 1$처럼 이웃한 두 숫자가 같은가 같지 않은가에 따라 $=$, $\ne$를 두 숫자 사이에 둘 때, $=$가 연속하지 않는 방법의 수와 같다. $n$개의 숫자를 위의 규칙에 따라 나열하는 방법의 수를 $f ( n )$이라 하자. $( n + 1 )$개의 숫자를 규칙에 따라 나열하는 방법은 $a _{1}$, $a _{2}$, $a _{3}$, $\cdots$, $a _{n} \ne a _{n + 1}$인 경우, $a _{1}$, $a _{2}$, $a _{3}$, $\cdots$, $a _{n - 1} \ne a _{n} = a _{n+1}$인 경우이므로 $f ( n + 1 ) = f ( n ) + f ( n - 1 )$ ($n \geq 2$)이다. $f ( 1 ) = 2$, $f ( 2 ) = 4$, $f ( 3 ) = 6$, $f ( 4 ) = 10$, $f ( 5 ) = 16$이다.