(자연계 수리논술) 점화식 관련

양의 정수 $n$ 에 대하여 집합 $A_n$ 을 $$A_n = \{(x_1, \; x_2, \; \cdots, \;x_n)\; |\; x_i \in \{1, \; 2, \; 3, \; 4\}, \; x_1 + x_2 + \cdots + x_n\; 은 \; 5의 \; 배수\}$$ 라 하고, $A_n$ 의 원소의 개수를 $a_n$ 이라 하자. 예를 들면, $$A_1 = \emptyset\; (공집합), \; \; A_2 = \{(1, \; 4), \;(2, \; 3), \; (3, \; 2), \; (4, \; 1)\}$$ 이므로 $a_1=0, \; a_2=4$ 이다. 또한 $(1, \; 1, \; 3) \in A_3$ 이다.

1) $a_3$ 의 값을 구하시오.

2) $n \ge 2$ 일 때, $a_n$ 과 $a_{n-1}$ 의 관계식을 구하시오.

3) $a_n$ 을 $n$ 의 식으로 나타내시오.

정답 (1) $12$   (2) $a_n + a_{n-1} = 4^{n-1}$   (3) $a_n = \dfrac{4}{5} \left ( 4^{n-1} - (-1)^{n-1} \right )$