연속 A 없는 문자열 개수

[출제의도] 수열의 귀납적 정의를 이용하여 수열의 일반항들 사이의 관계식을 구할 수 있는가를 묻는 문제이다. $a _{n}$을 문제의 조건을 만족시키는 $n$자리의 문자열의 개수라고 할 때 (ⅰ) 처음의 문자가 $\mathrm{B}$인 경우: 처음의 문자를 제외한 나머지 문자열들은 $\mathrm{A}$가 연속으로 $3$번 이상 나오지 않는 $( n - 1 )$자리수이며 이런 문자열의 개수는 $a _{n-1}$이다. (ⅱ) 처음의 문자가 $\mathrm{A}$인 경우: 이 경우 $\mathrm{A}$다음으로 $\mathrm{A}$또는 $\mathrm{B}$가 나올 수 있으므로 ① 처음 두 자리가 $\mathrm{AB}$인 경우: 처음의 두 자리의 문자열을 제외한 나머지 문자열들은 $\mathrm{A}$가 연속으로 $3$번 이상 나오지 않는 $( n - 2 )$자리수이며 이런 문자열의 개수는 $a _{n - 2}$이다. ② 처음 두 자리가 $\mathrm{AAB}$인 경우: 처음의 세 자리의 문자열을 제외한 나머지 문자열들은 $\mathrm{A}$가 연속으로 $3$번 이상 나오지 않는 $( n - 3 )$자리수이며 이런 문자열의 개수는 $a _{n - 3}$이다. 이제 위의 세 경우 모두 동시에 일어나지 않으므로 합의 법칙에 의해 $a _{n} = a _{n - 1} + a _{n - 2} + a _{n - 3} ( n \geq 4 )$ (단, $a _{1} = 2 , a _{2} = 4 , a _{3} = 7$ ) 이므로, $a _{6} = 44$이다.