수열의 귀납적 정의와 역추론
점화식의 분기 조건을 이용한 초기항 집합의 탐색
Q [문제 원문]
15. 첫째항이 자연수인 수열 $\{a_n\}$이 모든 자연수 $n$에 대하여
를 만족시킬 때, $a_6 + a_7 = 3$ 이 되도록 하는 모든 $a_1$의 값의 합은? [4점]
1 [출제의도]
이 문항은 수열의 귀납적 정의를 이해하고, 주어진 항들의 조건($a_6 + a_7 = 3$)으로부터 출발하여 점화식을 역으로 추적(Backtracking)하는 능력을 평가합니다. 특히, 역추적 과정에서 생성되는 값들이 분기 조건(홀수인지 짝수인지)을 만족하는지 검증하는 논리적 엄밀함을 묻고 있습니다.
2 [상세 풀이]
Step 1 : 초기 조건 분석 및 경우의 수 분할
첫째항 $a_1$이 자연수이고, 점화식의 연산(거듭제곱, 2로 나누기) 특성상 모든 항 $a_n$은 자연수입니다. 주어진 조건 $a_6 + a_7 = 3$ 을 만족하는 자연수의 순서쌍 $(a_6, a_7)$ 은 오직 두 가지뿐입니다.
- Case 1 : $a_6 = 1, a_7 = 2$
- Case 2 : $a_6 = 2, a_7 = 1$
참고 도형 1 : 초기 조건 검증
Step 2 : 역추적 로직 도출
$a_{n+1}$ 에서 $a_n$ 을 구하는 역연산 규칙을 수식으로 정리합니다.
참고 도형 2 : 역분기 트리 구조
Step 3 : Case 1 ($a_6 = 1$) 역추적
도출된 로직을 적용하여 $a_1$까지 수형도를 그립니다.
$\cdot \; a_6 = 1$
$\cdot \; a_5 = 2 \times 1 = \mathbf{2}$ $\quad (\log_2 1 = 0$ 은 자연수가 아니므로 제외$)$
$\cdot \; a_4 = 2 \times 2 = \mathbf{4}$ 또는 $\log_2 2 = \mathbf{1}$ (1은 홀수이므로 채택) $\implies a_4 \in \{1, 4\}$
$\cdot \; a_3$ 계산 :
$a_4=1$ 에서 $a_3 = \mathbf{2}$
$a_4=4$ 에서 $a_3 = 2 \times 4 = \mathbf{8}$ $\quad (\log_2 4 = 2$ 는 짝수이므로 제외$)$
$\implies a_3 \in \{2, 8\}$
$\cdot \; a_2$ 계산 :
$a_3=2$ 에서 $a_2 \in \{\mathbf{1}, \mathbf{4}\}$
$a_3=8$ 에서 $a_2 = 2 \times 8 = \mathbf{16}$ 또는 $\log_2 8 = \mathbf{3}$ (3은 홀수 채택)
$\implies a_2 \in \{1, 4, 3, 16\}$
$\cdot \; a_1$ 계산 :
$a_2=1 \implies a_1 = \mathbf{2}$
$a_2=4 \implies a_1 = \mathbf{8}$
$a_2=3 \implies a_1 = 2 \times 3 = \mathbf{6}$ $\quad (\log_2 3$ 불가$)$
$a_2=16 \implies a_1 = 2 \times 16 = \mathbf{32}$ $\quad (\log_2 16 = 4$ 는 짝수라 제외$)$
Step 4 : Case 2 ($a_6 = 2$) 역추적
$a_6 = 2$ 인 경우는 방금 구한 Case 1 의 $a_5 = 2$ 인 상황과 완벽히 동일합니다. 즉, 수열의 인덱스가 하나씩 밀리는 효과를 가집니다.
따라서 Case 2 의 $a_2$ 집합은 Case 1 의 $a_1$ 집합과 동일한 $\{2, 8, 6, 32\}$ 가 됩니다. 여기서 한 단계만 더 추적하면 됩니다.
$\cdot \; a_1$ 계산 (Case 2) :
$a_2=2 \implies a_1 \in \{\mathbf{1}, \mathbf{4}\}$
$a_2=8 \implies a_1 \in \{\mathbf{3}, \mathbf{16}\}$
$a_2=6 \implies a_1 = 2 \times 6 = \mathbf{12}$ $\quad (\log_2 6$ 불가$)$
$a_2=32 \implies a_1 = 2 \times 32 = \mathbf{64}$ 또는 $\log_2 32 = \mathbf{5}$ (홀수 채택)
Step 5 : 최종 합산
Case 1 과 Case 2 에서 구한 모든 가능한 $a_1$ 의 값들을 중복 없이 합산합니다.
3 [이론 매칭]
수열의 귀납적 정의
인접한 두 항 사이의 관계식(점화식)을 통해 수열의 모든 항을 정의하는 개념입니다.
로그의 정의 및 지수방정식
지수 형태의 점화식을 역으로 풀기 위해 $2^x = y \iff x = \log_2 y$ 관계를 사용합니다.
4 [실수 포인트 및 증명]
🚨 역추적 시 '분기 조건 검증' 누락
가장 많은 학생들이 오답을 내는 이유는 $a_n = \log_2(a_{n+1})$ 로 역계산한 값이 원래의 전제 조건인 '홀수'인지를 확인하지 않기 때문입니다.
수학적 증명 (귀류법) :
명제 : $a_{n+1} = 4$ 일 때, 역추적된 $a_n$ 은 $2$가 될 수 없다.
증명 : $a_n = 2$ 라고 가정하자.
원래의 점화식에 $a_n = 2$ 를 대입한다. $2$는 짝수이므로 아래쪽 분기를 타야 한다.
즉, $a_{n+1} = \frac{1}{2} \times 2 = 1$ 이 되어야 한다.
이는 $a_{n+1} = 4$ 라는 전제에 모순된다.
따라서 $a_n = \log_2 4 = 2$ 처럼 값이 구해지더라도, 그 값이 홀수가 아니라면 버려야 함이 증명된다. (증명 끝)
5 [핵심 이론 증명]
수열의 역함수 관점에서의 증명
주어진 점화식 $f(x) = \begin{cases} 2^x & (x \text{가 홀수}) \\ \frac{x}{2} & (x \text{가 짝수}) \end{cases}$ 는 정의역이 자연수 집합 $\mathbb{N}$ 인 함수입니다. 이 함수의 역상(Inverse image) $f^{-1}(y) = \{x \in \mathbb{N} \mid f(x) = y\}$ 를 구하는 것이 역추적의 본질입니다.
1. $x$가 짝수인 영역에서의 치역은 모든 자연수입니다. 따라서 임의의 자연수 $y$에 대해 $x = 2y$ 는 항상 존재하며 짝수입니다.
2. $x$가 홀수인 영역에서의 치역은 $2^1, 2^3, 2^5, \dots$ 즉 2의 홀수 거듭제곱수 집합입니다.
따라서 $y$가 이 형태일 때만 $x = \log_2 y$ 가 홀수로서 존재하게 됩니다.
수열 역추적 2D 동적 시뮬레이터
좌표평면 상에서 수열 항 번호($n$, x축)와 항의 값($a_n$, y축)을 플롯하여 수형도를 시각화합니다. 아래 슬라이더로 단계를 조작해보세요.
● Case 2 (a6=2)