자연계열 2번

$\displaystyle A_{3}=\{(1,1,3),(1,2,2),(1,3,1),(2,1,2),(2,2,1),(2,4,4),$$\displaystyle \qquad\ \ (3,1,1),(3,3,4),(3,4,3),(4,2,4),(4,3,3),(4,4,2)\}$이므로 $\displaystyle a_{3}=12$이다.

$\displaystyle B_{n}=\{\,(x_{1},x_{2},\cdots,x_{n})\mid x_{i}\in\{1,2,3,4\},\ x_{1}+x_{2}+\cdots+x_{n}\text{은 5의 배수가 아니다.}\,\}$이라 놓고, $\displaystyle b_{n}$을 집합 $\displaystyle B_{n}$의 원소의 개수라 하면, $\displaystyle a_{n}+b_{n}=4^{n}$, $\displaystyle a_{n}=b_{n-1}$이다.따라서 $\displaystyle a_{n}+a_{n-1}=4^{n-1}$이다.

(2-2)의 점화식으로부터$\displaystyle a_{n}=4^{n-1}-a_{n-1}$$\displaystyle =4^{n-1}-4^{n-2}+a_{n-2}=\ \cdots$$\displaystyle =4^{n-1}-4^{n-2}+4^{n-3}-\ \cdots\ +(-1)^{n-2}a_{2}$$\displaystyle =4^{n-1}-4^{n-2}+4^{n-3}-\ \cdots\ +(-1)^{n-2}4$$\displaystyle =\frac{4^{n-1}\left(1-\left(-\frac{1}{4}\right)^{n-1}\right)}{1-\left(-\frac{1}{4}\right)}=\frac{4}{5}\left(4^{n-1}-(-1)^{n-1}\right)$