점화식

• 상위 항목 : 수학 관련 정보, 수열
• 관련 항목 : 재귀함수

漸化式, 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]을 구했다고 하자. 그리고 새로운 수열 [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]는 주어진 열린 구간에서 연속인 어떠한 함수를 잡아도 상관 없다.