귀납적 수열 개수

$a _{k} = v$를 만족시키는 자연수 $k$의 개수를 $N \left( v \right)$라 하면 모든 자연수 $k$는 $k = 1$, $k = 3$, $k = 2 n$, $k = 4 n + 1$, $k = 4 n + 3$ ($n$은 자연수) 중 하나로 유일하게 나타낼 수 있으므로 $a _{k} = v$가 되는 경우는 다음과 같다. (ⅰ) $k = 1$일 때 $a _{1} = 1$이므로 $v = 1$일 때 $1$개 존재한다. (ⅱ) $k = 3$일 때 $a _{3} = 4$이므로 $v = 4$일 때 $1$개 존재한다. (ⅲ) $k = 2 n$ ($n \geq 1$)일 때 $a _{2 n} = a _{n} + 1 = v$에서 $a _{n} = v - 1$ 즉, $a _{n} = v - 1$을 만족하는 $n$의 개수와 같으므로 개수는 $N \left( v - 1 \right)$ (ⅳ) $k = 4 n + 1$ ($n \geq 1$)일 때 $a _{4 n + 1} = a _{n} + 4 = v$에서 $a _{n} = v - 4$ 즉, $a _{n} = v - 4$를 만족하는 $n$의 개수와 같으므로 개수는 $N \left( v - 4 \right)$ (ⅴ) $k = 4 n + 3$ ($n \geq 1$)일 때 $a _{4 n + 3} = a _{n} + 4 = v$에서 $a _{n} = v - 4$ 즉, $a _{n} = v - 4$를 만족하는 $n$의 개수와 같으므로 개수는 $N \left( v - 4 \right)$ 이상에서 $v \geq 5$일 때, $k = 1$이나 $k = 3$인 경우는 해당하지 않으므로 $N \left( v \right) = N \left( v - 1 \right) + 2 N \left( v - 4 \right)$ $v = 1$, $2$, $3$, $4$일 때 $N \left( 1 \right) = 1$ $N \left( 2 \right) = N \left( 1 \right) = 1$ $N \left( 3 \right) = N \left( 2 \right) = 1$ $N \left( 4 \right) = N \left( 3 \right) + 1 = 2$ ($k = 3$인 경우 $1$개 추가) $N \left( v \right) = N \left( v - 1 \right) + 2 N \left( v - 4 \right)$에 $v = 5$, $6$, $7$, $8$, $9$, $10$을 차례대로 대입하면 $N \left( 5 \right) = N \left( 4 \right) + 2 N \left( 1 \right) = 2 + 2 \times 1 = 4$ $N \left( 6 \right) = N \left( 5 \right) + 2 N \left( 2 \right) = 4 + 2 \times 1 = 6$ $N \left( 7 \right) = N \left( 6 \right) + 2 N \left( 3 \right) = 6 + 2 \times 1 = 8$ $N \left( 8 \right) = N \left( 7 \right) + 2 N \left( 4 \right) = 8 + 2 \times 2 = 12$ $N \left( 9 \right) = N \left( 8 \right) + 2 N \left( 5 \right) = 12 + 2 \times 4 = 20$ $N \left( 10 \right) = N \left( 9 \right) + 2 N \left( 6 \right) = 20 + 2 \times 6 = 32$ 따라서 $a _{k} = 10$을 만족시키는 자연수 $k$의 개수는 $32$이다. [다른 풀이] 모든 자연수 $n$에 대하여 $A$: $n \rightarrow 2 n$ $B$: $n \rightarrow 4 n + 1$ $C$: $n \rightarrow 4 n + 3$ 라 하면 모든 자연수 $k$는 $a _{1} = 1$, $a _{3} = 4$이므로 $1$ 또는 $3$에 대하여 위의 $A$, $B$, $C$를 적용하여 유일하게 결정된다. $A$를 적용한 횟수를 $x$, $B$ 또는 $C$를 적용한 횟수를 $y$라 하자. ($x$, $y$는 음이 아닌 정수) 이때 항의 값 $a _{k}$는 처음의 항의 값에 $x + 4 y$를 더한 것과 같다. 따라서 $a _{k} = 10$이 되는 경우는 $a _{1} = 1$인 경우와 $a _{3} = 4$인 경우로 나눌 수 있다. (ⅰ) $a _{1} = 1$, 즉 $a _{1}$에서 시작할 때 $a _{k} = 1 + x + 4 y = 10$이므로 $x + 4 y = 9$ 이를 만족시키는 음이 아닌 정수 $x$, $y$의 순서쌍 $\left( x , y \right)$는 $\left( 9 , 0 \right)$, $\left( 5 , 1 \right)$, $\left( 1 , 2 \right)$ $x + y$번 중 $B$ 또는 $C$가 들어갈 $y$개의 자리를 선택하고, 그 각각에 대해 $B$와 $C$ 중 하나를 선택하는 경우의 수는 $\mathit{_{x + y}} {\mathrm{C}} \mathit{_{y}} \times 2 ^{y}$이므로 $\left( x , y \right) = \left( 9 , 0 \right)$일 때 $\mathit{_{9}} {\mathrm{C}} \mathit{_{0}} \times 2 ^{0} = 1$ $\left( x , y \right) = \left( 5 , 1 \right)$일 때 $\mathit{_{6}} {\mathrm{C}} \mathit{_{1}} \times 2 ^{1} = 6 \times 2 = 12$ $\left( x , y \right) = \left( 1 , 2 \right)$일 때 $\mathit{_{3}} {\mathrm{C}} \mathit{_{2}} \times 2 ^{2} = 3 \times 4 = 12$ 따라서 처음의 값이 $1$인 자연수 $k$의 개수는 $1 + 12 + 12 = 25$ (ⅱ) $a _{3} = 4$, 즉 $a _{3}$에서 시작할 때 $a _{k} = 4 + x + 4 y = 10$이므로 $x + 4 y = 6$ 이를 만족시키는 음이 아닌 정수 $x$, $y$의 순서쌍 $\left( x , y \right)$는 $\left( 6 , 0 \right)$, $\left( 2 , 1 \right)$ $\left( x , y \right) = \left( 6 , 0 \right)$일 때 $\mathit{_{6}} {\mathrm{C}} \mathit{_{0}} \times 2 ^{0} = 1$ $\left( x , y \right) = \left( 2 , 1 \right)$일 때 $\mathit{_{3}} {\mathrm{C}} \mathit{_{1}} \times 2 ^{1} = 3 \times 2 = 6$ 따라서 처음의 값이 $3$인 자연수 $k$의 개수는 $1 + 6 = 7$ (ⅰ), (ⅱ)에 의하여 구하는 자연수 $k$의 개수는 $25 + 7 = 32$ [다른 풀이] 주어진 조건에 따라 모든 자연수 $k$는 짝수이거나 $1$, $3$ 또는 $4 n + 1$, $4 n + 3$의 형태 중 하나로 유일하게 나타낼 수 있다. 따라서 $a _{k} = m$을 만족하는 자연수 $k$의 개수를 차례대로 구하면 다음과 같다. (ⅰ) $a _{k} = 1$일 때 $k = 1$뿐이므로 $1$개이다. (ⅱ) $a _{k} = 2$일 때 $a _{n} + 1 = 2$에서 $a _{n} = 1$이므로 $n = 1$ 즉, $k = 2 \times 1 = 2$이므로 $1$개이다. (ⅲ) $a _{k} = 3$일 때 $a _{n} + 1 = 3$에서 $a _{n} = 2$이므로 $n = 2$ 즉, $k = 2 \times 2 = 4$이므로 $1$개이다. (ⅳ) $a _{k} = 4$일 때 주어진 조건에서 $a _{3} = 4$이므로 $k = 3$ 또한 $a _{n} + 1 = 4$에서 $a _{n} = 3$이므로 $n = 4$ 즉, $k = 2 \times 4 = 8$이므로 $k = 3$, $8$의 $2$개이다. (ⅴ) $a _{k} = 5$일 때 $a _{n} + 1 = 5$에서 $a _{n} = 4$이므로 $k$는 $2$개이다. $a _{n} + 4 = 5$에서 $a _{n} = 1$이므로 $n$은 $1$개이고, $k = 4 n + 1$, $4 n + 3$의 $2$개가 존재하므로 $1 \times 2 = 2$개이다. 따라서 $a _{k} = 5$일 때 $k$의 개수는 $2 + 2 = 4$ (ⅵ) $a _{k} = 6$일 때 $a _{n} + 1 = 6$에서 $a _{n} = 5$이므로 $k$는 $4$개이다. $a _{n} + 4 = 6$에서 $a _{n} = 2$이므로 $n$은 $1$개이고, $k$는 $1 \times 2 = 2$개이다 따라서 $a _{k} = 6$일 때 $k$의 개수는 $4 + 2 = 6$ (ⅶ) $a _{k} = 7$일 때 $a _{n} + 1 = 7$에서 $a _{n} = 6$이므로 $6$개, $a _{n} + 4 = 7$에서 $a _{n} = 3$이므로 $1 \times 2 = 2$개이다. 따라서 $a _{k} = 7$을 만족시키는 $k$의 개수는 $6 + 2 = 8$ (ⅷ) $a _{k} = 8$일 때 $a _{n} + 1 = 8$에서 $a _{n} = 7$이므로 $8$개, $a _{n} + 4 = 8$에서 $a _{n} = 4$이므로 $2 \times 2 = 4$개이다. 따라서 $a _{k} = 8$을 만족시키는 $k$의 개수는 $8 + 4 = 12$ (ⅸ) $a _{k} = 9$일 때 $a _{n} + 1 = 9$에서 $a _{n} = 8$이므로 $12$개, $a _{n} + 4 = 9$에서 $a _{n} = 5$이므로 $4 \times 2 = 8$개이다. 따라서 $a _{k} = 9$를 만족시키는 $k$의 개수는 $12 + 8 = 20$ (ⅹ) $a _{k} = 10$일 때 $a _{n} + 1 = 10$에서 $a _{n} = 9$이므로 $20$개, $a _{n} + 4 = 10$에서 $a _{n} = 6$이므로 $6 \times 2 = 12$개이다. 따라서 $a _{k} = 10$을 만족시키는 $k$의 개수는 $20 + 12 = 32$ 이상에서 $a _{k} = 10$을 만족시키는 $k$의 개수는 $20 + 12 = 32$