동차점화식의 일반항

개요

수열에서 점화식이란 이전항을 이용해 다음 항을 알아내는 식이다. 예를 들어 어떤 수열 $a$에 대해 다음 식은 모두 점화식이다.

1. $a_{n+1}=2a_n$
2. $a_{n+1}=a_n+4$
3. $a_{n+1}=3a_n+4$
4. $a_{n}=2a_{n-1}+3a_{n-2}$

이 중 식 1, 2, 3 꼴의 점화식에서 일반항을 유도하는 방법은 이미 이 글에서 다루었다. 이번 글에서는 4번 형식의 점화식에서 일반항을 구하는 방법에 대해 알아보자.

---

동차점화식과 비동차점화식

점화식은 꼴에 따라 2가지 형태로 나눌 수 있다.

1번 식과 같은 꼴의 점화식을 "동차점화식"이라고 하고 2번 식과 같은 꼴의 점화식을 비동차점화식이라고 한다.

1. $a_n=k_1 a_{n-1}+k_2 a_{n-2}+\cdots$$+k_m a_{n-m}$ (단 $n \geq m$)
2. $a_n=k_1 a_{n-1}+k_2 a_{n-2}+\cdots$$+k_m a_{n-m}+f(n)$ (단 $f(n)\neq 0$이고 $n \geq m$)

동차점화식과 비동차점화식의 차이는 수열의 항과 더불어 $n$에 관한 식(아니면 어떤 상수)이 붙냐 안 붙냐의 차이이다.

예를 들어 개요에서 언급한 $a_n=pa_{n-1}+q$꼴의 점화식은 비동차점화식이다.

 

일반적으로 비동차점화식은 동차점화식에 비해 풀기(여기서 푼다는 것은 일반항을 얻는 것) 어렵다. 이번 글에서는 동차점화식, 그중 특수한 경우를 푸는 방법에 대해서만 알아보겠다.

---

수열의 항이 3개인 동차점화식의 해법

우리가 풀 점화식의 형태는 다음과 같다.

$a_n=pa_{n-1}+qa_{n-2}$, 초기 조건으로 2개 항의 값을 알고 있음.

$a_n$의 계수가 1이 아니면 전 항에 $a_n$의 계수를 나누면 되기 때문에 $a_n$의 계수가 1인 것은 상관이 없다.

 

이 점화식을 푸는 방법부터 설명하자면 다음과 같다.

1. 식을 $a_n-pa_{n-1}-qa_{n-2}$ 로 이항
2. $C(t)=t^2-pt-q=0$ 으로 특성 방정식 작성
3. 특성 방정식의 해($C(t)=0$이 되게 하는 $t$의 값)를 각각 $\alpha$, $\beta$라고 하자.

이제 두 근 $\alpha$와 $\beta$에 따라 방법이 나뉜다.

 

$\alpha=\beta=t$인 경우:

$a_n=(P_0+P_1n)t^n$

$P_0$과 $P_1$의 값은 초기 조건으로 주어진 항 2개의 값을 대입하여 각각 구한다.

 

$\alpha \neq \beta$인 경우:

$a_n=P_0\alpha^n+P_1\beta^n$

$P_0$과 $P_1$의 값은 초기 조건으로 주어진 항 2개의 값을 대입하여 각각 구한다.

 

---

수열의 항이 3개인 동차점화식 풀기

이 글의 3절에서는 풀이법만을 설명하였다. 이제 그 풀이가 왜 나왔는지 설명하겠다.

우선 다음과 같은 점화식이 있다고 하자.

$pa_{n+2}+qa_{n+1}+ra_n=0$

식 1

 

이 점화식의 양 변을 $p$로 나누어 수열의 가장 앞에 있는 항의 계수를 1로 맞춘다.

$a_{n+2}+\frac{q}{p}a_{n+1}+\frac{r}{p}a_n=0$

식 2

 

이 식의 $a_{n+2}=x^2$, $a_{n+1}=x$, $a_n=1$이라고 하여 대입하면 다음과 같은 이차방정식이 나온다.

$x^2+\frac{q}{p}x+\frac{r}{p}=0$

이 식을 특성 방정식이라고 한다.

 

특성 방정식인 이차방정식에서 근과 계수의 관계를 사용하여 두 근($\alpha$, $\beta$)의 합과 곱을 구하면 다음과 같다.

$\alpha+\beta=-\frac{q}{p}$, $\alpha\beta=\frac{r}{p}$

 

이 값을 식 2에 대입하면 다음과 같다.

$a_{n+2}-(\alpha+\beta)a_{n+1}+(\alpha\beta)a_n=0$

 

항을 전개한 후 적절히 이항 하고 공통 인수를 묶으면 위 식은 다음과 같이 변형된다.

$a_{n+2}-\alpha a_{n+1}=\beta(a_{n+1}-\alpha a_n)$

 

이제 새로운 수열 $b_n$을 정의하여 $b_n=a_{n+1}-\alpha a_{n}$이라고 하자. 그럼 위의 식은 새로운 수열 $b_n$을 이용하여 다음과 같이 쓸 수 있다.

$b_{n+1}=\beta b_{n}$

 

위와 같은 점화식을 가진 수열은 등비수열로 일반항은 다음과 같이 쓸 수 있다.

$b_{n}=b_0 \beta ^{n}$

 

수열 $b_n$을 $a_n$으로 돌려놓으면 다음과 같다.

$a_{n+1}-\alpha a_{n}=(a_1-\alpha a_0)\beta^{n}$

 

$\alpha$와 $\beta$는 이차방정식의 두 근이니까 순서가 바뀔 수 있다. 따라서 다음과 같이 식 2개를 쓸 수 있다.

1. $a_{n+1}-\alpha a_{n}=(a_1-\alpha a_0)\beta^{n}$
2. $a_{n+1}-\beta a_{n}=(a_1-\beta a_0)\alpha^{n}$

위의 식 2에서 식 1을 빼면 다음과 같다.

$(\alpha-\beta)a_n=(\alpha^n -\beta^n)a_1$$-(\beta\alpha^n-\alpha\beta^n)a_0$

 

이 식을 $\alpha^n$과 $\beta^n$으로 묶어 정리하면 다음과 같다.

$(\alpha-\beta)a_n=\alpha^n(a_1-\beta a_0)$$-\beta^n(a_1-\alpha a_0)$

 

따라서 최종적인 일반항은 다음과 같이 구할 수 있다.

$a_n=\frac{a_1-\beta a_0}{\alpha-\beta}\alpha^n$$+\frac{\alpha a_0-a_1}{\alpha-\beta}\beta^n$

 

여기서 $\frac{a_1-\beta a_0}{\alpha-\beta}=P_0$, $\frac{\alpha a_0-a_1}{\alpha-\beta}=P_1$이라고 하면 다음과 같이 일반항을 쓸 수 있다.

$a_n=P_0\alpha^n+P_1\beta^n$

 

원래대로라면 $P_0$와 $P_1$의 위치에 각각 $\alpha$와 $\beta$의 값을 넣어서 계산을 해야 하지만 굳이 그럴 것은 없다. 2개 항의 값을 초기 조건으로 알고 있기 때문에 그 값을 $a_n$에 대입하고 $\alpha$와 $\beta$에 각각 제 값을 대입하여 연립방정식을 통해 $P_0$와 $P_1$의 값을 알 수 있다.

 

하지만 만약 $\alpha=\beta$인 경우 양변을 $\alpha-\beta$로 나누는 과정에서 오류가 생기기 때문에 이 식을 사용할 수 없다. 따라서 $\alpha=\beta$인 경우 적용되는 다른 식이 필요하다. 하지만 이 부분은 필자의 지식이 부족한지라(...) 쓰진 못하겠다...