점화식

漸化式, Recurrence relation.

1 개요

어떤 수열의 각각의 항들의 관계를 나타낸 식이다.

2 정의

점화식을 집합론적인 관점에서 살펴본다면, 다음과 같이 나타낼 수 있다.

[math]\omega[/math]를 자연수의 집합이라 하자.(보통 집합론에서는 natural number에 0을 포함시킨다.) 집합 [math]A[/math] 대해서, 함수 [math]f:A\to A[/math]와 어떤 원소 [math]c\in A[/math]를 생각하자. 이 때, 다음을 만족하는 함수 [math]\gamma:\omega\to A[/math]가 유일하게 존재한다:

 i. [math]\gamma\left(0\right)=c[/math]
 i. [math]\gamma\left(n^+\right)=f\left(\gamma\left(n\right)\right), \: \forall n\in\omega[/math]

이 때, [math]c[/math]가 초항, [math]f[/math]가 점화식, 그리고 [math]\gamma[/math]가 일반항이라고 생각하면 된다. 자연수 사이의 연산 역시 점화식의 형태로 정의된다. 자연수 사이의 연산(더 정확하게는 덧셈)이 정의되고 나면, 다음과 같은 일반적인 상황에서의 Theorem을 만들어낼 수 있다.

[math]\omega[/math]를 자연수의 집합이라 하고,[math]k\in \omega[/math]일 때 [math]\omega_k=\left\{0,1,\cdots,k\right\}[/math]라 하자.. 집합 [math]A[/math] 대해서, 함수 [math]f:A^{k+1}\to A[/math]와 순서쌍 [math]c=\left(c_0,c_1,\cdots,c_k\right)\in A^{k+1}[/math]를 생각하자. 이 때, 다음을 만족하는 함수 [math]\gamma:\omega\to A[/math]가 유일하게 존재한다:

 i. [math]\gamma\left(i\right)=c_i, \; \forall i\in \omega_k[/math]
 i. [math]\gamma\left(n+k+1\right)=f\left(\gamma(n),\gamma(n+1),\cdots,\gamma(n+k)\right), \: \forall n\in \omega[/math]

즉, 어떠한 함수 [math]f[/math]와 초기조건 [math]c[/math]에 대해서도, 점화식의 일반항 [math]\gamma\left(n\right)[/math]을 항상 찾을 수 있고, 그것은 유일하다. 물론, 찾을 수 있다 뿐이지, 그것을 closed form으로 나타내는 것은 쉽지 않다. 단순하게, 다음과 같은 점화식의 closed form을 찾기는 매우 어려움을 알 수 있다.

 i. [math]\gamma\left(0\right)=7[/math]
 i. [math]\gamma\left(n^+\right)=2^{\gamma\left(n\right)}-{\gamma\left(n\right)}^2, \: \forall n\in\omega[/math]

3 선형 점화식

수열 [math]\{a_n\}[/math]에 대하여 [math]\ a_{n+k}+c_1 a_{n+k-1}+c_2 a_{n+k-2}+\cdots+c_k a_n=f(n) [/math] 의 형태의 점화식을 선형 점화식이라고 한다. (단, [math] c_1, \cdots,c_k[/math]는 상수, [math]c_k \neq 0 [/math])

여기서 [math]f(n)=0[/math]이면 동차 선형 점화식이라 하고, [math]f(n) \neq 0[/math]이면 비동차 선형 점화식이라 한다. 비동차 선형 점화식을 동차 선형 점화식으로 바꾸면 일반항을 구하기가 쉬워지는데, 그렇게 만드는 방법은 특수해를 구하는 것이다.

특수해 [math]\{b_n\}[/math]을 구했다고 하자.[1] 그리고 새로운 수열 [math]\{x_n\}[/math][math]x_n = a_n -b_n[/math]으로 정의한다. 그러면 수열[math]\{x_n\}[/math]에 대한 점화식은 [math]\ x_{n+k}+c_1 x_{n+k-1}+...+c_k x_n=0 [/math]이 된다. 이로써 특수해만 구할 수 있다면 비동차 선형 점화식은 동차 선형 점화식으로 바꿀 수 있음을 알 수 있다.

이때, [math]r [/math]에 대한 방정식 [math]r^k+c_1r^{k-1}+\cdots+c_k=0 [/math]을 이 점화식의 특성방정식이라 한다. 결론부터 말하자면, 특성방정식의 근이 [math]\alpha_1, \alpha_2, \cdots , \alpha_k [/math] 이면 [math]x_n [/math][math]{\alpha_1}^n, {\alpha_2}^n, \cdots , {\alpha_k}^n [/math]의 일차결합으로 나타내어진다. 즉, [math]x_n [/math]의 가능한 모든 일반항은 [math]x_n=A_1{\alpha_1}^n + A_2{\alpha_2}^n+ \cdots + A_k{\alpha_k}^n [/math]로 나타내어진다. ([math]A_1, A_2, \cdots ,A_k [/math]는 상수) 따라서 [math]a_n=b_n+x_n=b_n+A_1{\alpha_1}^n + A_2{\alpha_2}^n+ \cdots + A_k{\alpha_k}^n [/math]가 된다.

단, 여기서 [math]\alpha_1, \alpha_2, \cdots , \alpha_k [/math]는 모두 서로 달라야 한다. 만약 이 중 서로 같은 것들이 있다면, 즉 특성방정식이 중근을 갖는다면 일반항은 약간 달라진다. 어떤 근 [math]\beta [/math]가 중복수가 m인 중근이라면 [math]{\beta}^n, n{\beta}^n, \cdots , n^{m-1}{\beta}^n [/math]으로 대신해 일차결합을 해야 한다.

3.1 증명

동차 선형 점화식 [math]a_{n+k}+c_1 a_{n+k-1}+c_2 a_{n+k-2}+\cdots+c_k a_n=0 [/math]의 특성 방정식이 중근을 갖지 않는 경우만 증명한다.

[math]r [/math]에 대한 방정식 [math]r^k+c_1r^{k-1}+\cdots+c_k=0 [/math]이 근 [math]\alpha_1[/math]을 가졌다면 [math]\left(r- \alpha_1 \right) \left(r^{k-1}+d_1 r^{k-2}+ \cdots+d_{k-1}\right)=0 [/math]으로 인수분해가 된다. 그러면 이 계수들을 이용해 위 점화식을 다음과 같이 변형할 수 있다.

[math]a_{n+k}+d_1 a_{n+k-1}+\cdots+d_{k-1}a_{n+1}=\alpha_1 \left(a_{n+k-1}+d_1 a_{n+k-2}+\cdots+d_{k-1}a_n\right)[/math]

이는 간단한 점화식이므로 [math]a_1, a_2, \cdots, a_k[/math]의 값이 정해져 있을 때 다음과 같이 된다.

[math]a_{n+k}+d_1 a_{n+k-1}+\cdots+d_{k-1}a_{n+1}={\alpha_1}^{n} \left(a_{k}+d_1 a_{k-1}+\cdots+d_{k-1}a_1\right)={\alpha_1}^{n}C_1[/math] ([math]C_1[/math]은 상수)

여기서 특수해로 [math]\left\{C{\alpha_1}^{n}\right\}[/math]을 가정하면

[math]C{\alpha_1}^{n}\left({\alpha_1}^{k}+d_1 {\alpha_1}^{k-1}+\cdots+d_{k-1}\alpha\right)={\alpha_1}^{n}C_1[/math]

특성방정식이 중근을 가지지 않으므로 [math]{\alpha_1}^{k}+d_1 {\alpha_1}^{k-1}+\cdots+d_{k-1}\alpha\neq 0[/math]이다. 따라서

[math]\displaystyle C={C_1\over {\alpha_1}^{k}+d_1 {\alpha_1}^{k-1}+\cdots+d_{k-1}\alpha}[/math]로 놓을 수 있다. 이 값을 [math]A_1[/math]이라 하자. 그러면 [math] b_n=a_n-A_1{\alpha_1}^{n}[/math]이라 정의할 때 수열 [math]\left\{b_n\right\}[/math]의 점화식은 다음과 같게 된다.

[math]b_{n+k-1}+d_1 b_{n+k-2}+\cdots+d_{k-1}b_{n}=0[/math]

이러한 과정을 반복해 나가면 수열 [math]\left\{a_n\right\}[/math]의 일반항은 [math]a_1, a_2, \cdots, a_k[/math]에 따라 정해지는 상수 [math]A_1, A_2, \cdots ,A_k [/math]에 대하여 다음과 같은 꼴로 표현됨을 알 수 있다.

[math]a_n=A_1{\alpha_1}^n + A_2{\alpha_2}^n+ \cdots + A_k{\alpha_k}^n [/math]

4 미분방정식에서의 응용

미분방정식의 해 역시 점화식의 형태로 나타낼 수 있다.

다음과 같은 상미분방정식을 생각하자.

[math]\displaystyle y_1=F_1\left(t,y_1,y_2,\cdots,y_n\right),\, y_1\left(0\right)=p_1[/math]
[math]\displaystyle y_2=F_2\left(t,y_1,y_2,\cdots,y_n\right),\, y_2\left(0\right)=p_2[/math]
[math]\displaystyle \quad\qquad\qquad\qquad \vdots[/math]
[math]\displaystyle y_n=F_n\left(t,y_1,y_2,\cdots,y_n\right),\, y_n\left(0\right)=p_n[/math]

만약 각각의 [math]F_i[/math][math]\frac{\partial F_i}{\partial y_j}[/math][math]\left(0,p_1,p_2,\cdots,p_n\right)[/math]을 포함한 어떤 열린 영역에서 연속이라면, [math]0[/math]을 포함하는 열린 구간에서 미분방정식의 해는 존재하고 유일하며, 다음과 같은 점화식의 극한의 형태로 나타내어진다(Picard's Existence Theorem):

[math]\displaystyle y_{1,k+1}\left(t\right)=p_1+\int_0^t{F_1\left(s,y_{1,k}\left(s\right),y_{2,k}\left(s\right),\cdots,y_{n,k}\left(s\right)\right)ds}[/math]
[math]\displaystyle y_{2,k+1}\left(t\right)=p_2+\int_0^t{F_2\left(s,y_{1,k}\left(s\right),y_{2,k}\left(s\right),\cdots,y_{n,k}\left(s\right)\right)ds}[/math]
[math]\displaystyle \qquad\qquad\qquad\qquad\qquad\qquad \vdots[/math]
[math]\displaystyle y_{n,k+1}\left(t\right)=p_n+\int_0^t{F_n\left(s,y_{1,k}\left(s\right),y_{2,k}\left(s\right),\cdots,y_{n,k}\left(s\right)\right)ds}[/math]

초기조건 [math]\displaystyle y_{1,0}\left(t\right),y_{2,0}\left(t\right),\cdots,y_{n,0}\left(t\right)[/math]는 주어진 열린 구간에서 연속인 어떠한 함수를 잡아도 상관 없다.
  1. 특수해를 구하는 요령은 f(n)이 상수이면 보통 어떤 상수로 특수해를 추측해 보는 것이고, f(n)이 m차식이면 특수해도 m차식으로 추측해 보는 것이다. 하지만 일반적인 방법은 없다.