앞의 항들로 다음 항을 정하는 식을 점화식이라 한다. 직접 세기 어려운 문제도 ‘크기가 하나 작은 문제’와의 관계를 찾으면 점화식으로 풀 수 있다. 하노이의 탑, 계단 오르기, 피보나치 수열이 대표적이다.
핵심 개념
- 일차 점화식: $a_{n+1}=pa_n+q$ ($p\neq1$)는 $a_{n+1}-\alpha=p(a_n-\alpha)$ ($\alpha=\frac{q}{1-p}$)로 바꾸면 등비수열이 된다.
- 이계 선형 점화식 $a_{n+2}=pa_{n+1}+qa_n$: 특성방정식 $x^2=px+q$의 두 근 $\alpha\neq\beta$에 대해 $a_n=A\alpha^n+B\beta^n$
핵심 정리 (비네 공식)
피보나치 수열 $F_1=F_2=1$, $F_{n+2}=F_{n+1}+F_n$의 일반항은
$$F_n=\frac{1}{\sqrt5}\left[\left(\frac{1+\sqrt5}{2}\right)^n-\left(\frac{1-\sqrt5}{2}\right)^n\right]$$
증명 보기
아이디어. $a_n=x^n$ 꼴의 해를 찾는다. $x^{n+2}=x^{n+1}+x^n$이면 $x^2=x+1$이다. 두 근을 $\alpha=\frac{1+\sqrt5}2$, $\beta=\frac{1-\sqrt5}2$라 하자.
1단계: 일차결합도 해이다. $\alpha^n$과 $\beta^n$이 모두 점화식을 만족하고 점화식이 선형이므로 $A\alpha^n+B\beta^n$도 만족한다.
2단계: 처음 두 항 맞추기. $A\alpha+B\beta=1$, $A\alpha^2+B\beta^2=1$을 풀면 $A=\frac{1}{\sqrt5}$, $B=-\frac1{\sqrt5}$이다. ($\alpha-\beta=\sqrt5$, $\alpha^2=\alpha+1$을 이용)
3단계: 유일성. 점화식은 처음 두 항이 정해지면 나머지가 모두 정해지므로, 처음 두 항이 같은 두 수열은 같다. 따라서 $F_n=\frac{\alpha^n-\beta^n}{\sqrt5}$이다. $\blacksquare$
$|\beta|<1$이므로 $n$이 커지면 $\beta^n\to0$이고 $\frac{F_{n+1}}{F_n}\to\alpha\approx1.618$ (황금비)이다.
예제
- 하노이의 탑: 원판 $n$개를 옮기는 최소 횟수 $h_n$은 위의 $n-1$개를 옮기고, 가장 큰 원판을 옮기고, 다시 $n-1$개를 옮기므로 $h_n=2h_{n-1}+1$, $h_1=1$. $h_n+1=2(h_{n-1}+1)$이므로 $h_n=2^n-1$
- 계단 오르기: 한 번에 $1$칸 또는 $2$칸씩 $n$칸을 오르는 방법 $s_n=s_{n-1}+s_{n-2}$ (마지막 걸음이 $1$칸인지 $2$칸인지), $s_1=1$, $s_2=2$이므로 $s_n=F_{n+1}$
확인 문제
$a_1=1$, $a_{n+1}=3a_n+2$의 일반항을 구하시오.
풀이 보기
$\alpha=\frac{2}{1-3}=-1$이므로 $a_{n+1}+1=3(a_n+1)$이다. $a_n+1$은 첫째항 $2$, 공비 $3$인 등비수열이므로 $a_n=2\cdot3^{n-1}-1$이다.
정리
- 크기 $n$인 문제를 크기 $n-1$, $n-2$인 문제로 나누면 점화식이 나온다.
- 선형 점화식은 특성방정식의 근으로 푼다.
