점화식과 행렬

$pa_{n+2}+qa_{n+1}+ra_n=0$의 일반항을 구하는 방법을 대략적으로 알아보자. 주어진 식을 등비수열의 형태로 나타내기 위해 $$(a_{n+2}-{\alpha}a_{n+1})-\beta(a_{n+1}-\alpha{a_n})=0$$로 변형한 후, $$a_{n+1}-{\alpha}a_n=b_n$$으로 두고 푼다. 이때 $\alpha$와 $\beta$는 $px^2+qx+r=0$이라는 특성방정식의 해이다.

 

하지만 이렇게 식을 변형해 푸는 과정들은 직관에 의한 결과라기 보다는 이미 다른 방식으로 유도한 결과를 아는 상태에서 "신들린 테크닉"을 쓴 것 처럼 포장됐을 가능성도 있다. 따라서 조금 더 합리적으로, 새로운 방식으로 점화식을 푸는 과정을 소개해보겠다.

 

선형대수적 접근을 통해 우선 $pa_{n+2}+qa_{n+1}+ra_n=0$을 다음과 같은 선형 변환으로 나타내고자 한다.

$$\begin{pmatrix}a_{n+2}\\a_{n+1}\end{pmatrix}=A\begin{pmatrix}a_{n+1}\\a_n\end{pmatrix}={A^2}\begin{pmatrix}a_n\\a_{n-1}\end{pmatrix}={A^n}\begin{pmatrix}a_2\\a_1\end{pmatrix}$$

즉, 위의 식을 만족하는 $A$을 찾고 싶다. 이 $A$을

$$A=\begin{pmatrix}a&b\\c&d\end{pmatrix}$$

라 하면 두 식 $a_{n+2}=aa_{n+1}+ba_n$, $a_{n+1}=ca_{n+1}+da_n$에서 $a=-\frac{q}{p}$, $b=-\frac{q}{p}$, $c=1$, $d=0$이라 할 수 있다. 따라서

$$A=\begin{pmatrix}{-\frac{q}{p}}&{-\frac{q}{p}}\\1&0\end{pmatrix}$$

을 정의하면, 풀고 싶어하는 점화식 $pa_{n+2}+qa_{n+1}+ra_n=0$을

$$\begin{pmatrix}a_{n+2}\\a_{n+1}\end{pmatrix}=\begin{pmatrix}{-\frac{q}{p}}&{-\frac{q}{p}}\\1&0\end{pmatrix}\begin{pmatrix}a_{n+1}\\a_n\end{pmatrix}$$

으로 나타낼 수 있다. 여기서 $A^n$을 일반적으로 알 수 있다면

$$\begin{pmatrix}a_{n+2}\\a_{n+1}\end{pmatrix}={A^n}\begin{pmatrix}a_2\\a_1\end{pmatrix}$$

이므로 $a_n$의 일반항을 구할 수 있다는 것이다.

 

하지만 $$A^n={\begin{pmatrix}{-\frac{q}{p}}&{-\frac{q}{p}}\\1&0\end{pmatrix}}^n$$을 막연히 계산할 수 없으므로 우리는 $A=PDP^{-1}$꼴로 고치는 대각화를 한다. 이때 $P$는 가역행렬이고 $D$는 대각행렬의 꼴이다. 이때 $PP^{-1}=I$은 항등행렬이기 때문에, $$A^n=PDP^{-1}PDP^{-1}\cdots PDP^{-1}=PD^nP^{-1}=PD^nP^{-1}$$의 형태로 간단해질 수 있다. 이것이 간단한 이유는 대각행렬

$$D=\begin{pmatrix}\lambda_1&0\\0&\lambda_2\end{pmatrix}$$

은 이의 거듭제곱을 $$D^n=\begin{pmatrix}{\lambda_1}^n&0\\0&{\lambda_2}^n\end{pmatrix}$$

처럼 간단히 연산 할 수 있기 때문이다.

 

대각화를 하기 위해서는 $A$의 고윳값과 고유벡터를 알아야 한다. 벡터 $x=(x_1, x_2)$와 스칼라 $\lambda$에 대해 $Ax={\lambda}x$를 만족하는 $\lambda$와 $x$를 각각 고윳값과 고유벡터라 한다. $Ax={\lambda}x$를 $Ax={\lambda}Ix$로 고친 뒤 $(A-{\lambda}I)x=0$을 풀어야 하고 이때 $x$는 영벡터가 아니므로 $A-{\lambda}I$가 비가역행렬이여야 한다. 따라서 $det(A-{\lambda}I)=0$이여야 한다.

$$A-{\lambda}I=\begin{pmatrix}{-\frac{q}{p}}&{-\frac{q}{p}}\\1&0\end{pmatrix}-\begin{pmatrix}\lambda&0\\0&\lambda\end{pmatrix}=\begin{pmatrix}{-\frac{q}{p}-\lambda}&{-\frac{q}{p}}\\1&-\lambda\end{pmatrix}$$

이고 $$det(A-{\lambda}I)=(-\frac{q}{p}-\lambda)(-\lambda)+\frac{r}{p}={\lambda}^2+{\frac{q}{p}}\lambda+\frac{r}{p}=0$$의 두 근 ${\lambda}_1$, ${\lambda}_2$은 고윳값이라고 한다. $\lambda$는 고윳값이므로 식 $Ax={\lambda}Ix$을 만족하고,

$$\begin{pmatrix}{-\frac{q}{p}}&{-\frac{q}{p}}\\1&0\end{pmatrix}\begin{pmatrix}x_1\\x_2\end{pmatrix}=\begin{pmatrix}{\lambda}x_1\\{\lambda}x_2\end{pmatrix}$$이므로 $-\frac{q}{p}x_1-\frac{r}{p}x_2={\lambda}x_1$이다. $x_1={\lambda}x_2$이므로 이때 구한 $x=(x_1, x_2)$는 고유벡터가 된다. 고윳값이 2개이므로 고유벡터 또한 2개이다.

 

$x'=\begin{pmatrix}x_1\\x_2\end{pmatrix}=\begin{pmatrix}{\lambda}_1{x_2}\\x_2\end{pmatrix}=x_2\begin{pmatrix}{\lambda}_1\\1\end{pmatrix}$, $x''=\begin{pmatrix}x_1\\x_2\end{pmatrix}=x_2\begin{pmatrix}{\lambda}_2\\1\end{pmatrix}$

라 하자. $Ax={\lambda}x$에서

$$Ax=A\begin{pmatrix}{\lambda}{x_2}\\x_2\end{pmatrix}={\lambda}\begin{pmatrix}{\lambda}{x_2}\\x_2\end{pmatrix}=\begin{pmatrix}{{\lambda}^2}{x_2}\\{\lambda}x_2\end{pmatrix}$$

이다. 따라서,

$Ax'=\begin{pmatrix}{{{\lambda}_1}^2}x_2\\{{\lambda}_1}x_2\end{pmatrix}$, $Ax''=\begin{pmatrix}{{{\lambda}_2}^2}x_2\\{{\lambda}_2}x_2\end{pmatrix}$

이다. 이때

$$P=\begin{pmatrix}{{{\lambda}_1}^2}x_2&{\lambda}_2{x_2}\\x_2&x_2\end{pmatrix}$$

라 하면

$$AP=A\begin{pmatrix}{{{\lambda}_1}^2}x_2&{\lambda}_2{x_2}\\x_2&x_2\end{pmatrix}=\begin{pmatrix}{{{\lambda}_1}^2}x_2&{{\lambda}_2}^2{x_2}\\{\lambda}_1{x_2}&{\lambda}_2{x_2}\end{pmatrix}=\begin{pmatrix}{{{\lambda}_1}^2}x_2&{\lambda}_2{x_2}\\x_2&x_2\end{pmatrix}\begin{pmatrix}{\lambda}_1&0\\0&{\lambda}_2\end{pmatrix}=P\begin{pmatrix}{\lambda}_1&0\\0&{\lambda}_2\end{pmatrix}$$가 된다. 여기서

$$\begin{pmatrix}{\lambda}_1&0\\0&{\lambda}_2\end{pmatrix}=D$$라 하자. 그러면, $D$는 대각 행렬이고 $AP=PD$이므로 따라서 $A=PDP^{-1}$이다. $$A^n=PD^{n}P^{-1}={x_2}\begin{pmatrix}{\lambda}_1&{\lambda}_2\\1&1\end{pmatrix}\begin{pmatrix}{{\lambda}_1}^n&0\\0&{{\lambda}_2}^n\end{pmatrix}\frac{1}{x_2({\lambda}_1-{\lambda}_2)}\begin{pmatrix}1&-{\lambda}_2\\-1&{\lambda}_1\end{pmatrix}$$ 이다. 따라서

$$A^n=\frac{1}{{\lambda}_1-{\lambda}_2}\begin{pmatrix}{\lambda}_1&{\lambda}_2\\1&1\end{pmatrix}\begin{pmatrix}{{\lambda}_1}^n&0\\0&{{\lambda}_2}^n\end{pmatrix}\begin{pmatrix}1&-{\lambda}_2\\-1&{\lambda}_1\end{pmatrix}$$ 앞에서 봤듯이 $$\begin{pmatrix}a_{n+2}\\a_{n+1}\end{pmatrix}={A^n}\begin{pmatrix}a_2\\a_1\end{pmatrix}$$이므로 $$a_{n+2}=\frac{a_2-{{\lambda}_2}a_1}{{\lambda}_1-{\lambda}_2}{{\lambda}_1}^n-\frac{a_2-{{\lambda}_1}a_1}{{\lambda}_1-{\lambda}_2}{{\lambda}_2}^n$$ 정리하면, $$a_n=\frac{a_2-{\beta}a_1}{\alpha-\beta}{\alpha}^{n-1}-\frac{a_2-{\alpha}a_1}{\alpha-\beta}{\beta}^{n-1}$$이다. 즉, $$a_n={C_1}{\alpha}^{n-1}+{C_2}{\beta}^{n-1}$$의 꼴로 나타낼 수 있게 된다.

 

Exponential 17 김주원 18 윤정혁