선형점화식 문서 원본 보기


== 정의 ==
[[수열]] <math>(a_n)</math>의 [[점화식]]이
: <math>a_{n+d}=\sum_{i=0}^{d-1}c_i a_{n+i}+f(n)\quad(c_0\ne 0)</math>
꼴로 표현될 때, 이 식을 차수(degree) <math>d</math>인 '''선형점화식(linear recurrence relation)'''이라고 한다. 이때 <math>c_0,c_1,\cdots, c_{d-1}</math>은 상수이고 <math>f</math>는 [[산술적 함수]]이다.

== 예시 ==
* <math>a_{n+1}=a_n+3</math>: [[등차수열]]의 일종으로, 이 수열의 일반항은 <math>a_n=3n+c</math>이며 <math>c</math>는 임의의 상수이다.
* <math>a_{n+1}=2a_n</math>: [[등비수열]]의 일종으로, 이 수열의 일반항은 <math>a_n= c \cdot 2^n</math>이며 <math>c</math>는 임의의 상수이다.
* <math>a_{n+2}=a_{n+1}+a_n</math>: [[피보나치 수열]]과 [[루카스 수]]의 점화식이다. <math>a_0=0,a_1=1</math>이면 피보나치 수열, <math>a_0=2,a_1=1</math>이면 루카스 수가 된다.
* <math>a_{n+2}=2a_{n+1}-a_n</math>: 이 수열의 일반항은 <math>a_n = c_1+c_2n</math>이며, <math>c_1,c_2</math>는 임의의 상수이다.
* <math>a_{n+1}=3a_n + 2n</math>: 이 수열의 일반항은 <math>a_n=-n-\frac{1}{2}+c \cdot 3^n</math>이다.

== 기본 성질 ==
{{참고|수열공간}}
[[복소수]]를 항으로 가지는 모든 수열의 [[집합|집합]]을 <math>V</math>라고 하자. <math>V</math>의 원소 <math>(a_n),(b_n)</math>과 임의의 상수 <math>c</math>에 대해 벡터 덧셈과 스칼라곱을 다음과 같이 정의하자.
: <math>(a_n)+(b_n)=(a_n+b_n)</math>
: <math>c(a_n)=(ca_n)</math>
그러면 <math>V</math>는 [[벡터공간]]이 된다.
수열 <math>(a_n)</math>의 점화식이
: <math>a_{n+d}=\sum_{i=0}^{d-1}c_i a_{n+i}</math>
이고, <math>(a_n)</math>의 점화식을 만족하는 모든 수열의 집합을 <math>W</math>라고 하자. 그러면 <math>W</math>가 <math>V</math>의 부분집합임은 자명하다. 이제 <math>W</math>가 <math>V</math>의 부분공간임을 보이자. <math>W</math>의 임의의 원소 <math>(p_n),(q_n)</math>에 대해
: <math>p_{n+d}=\sum_{i=0}^{d-1}c_i p_{n+i}</math>
: <math>q_{n+d}=\sum_{i=0}^{d-1}c_i q_{n+i}</math>
이므로
: <math>\begin{align}
p_{n+d}+q_{n+d}&=\sum_{i=0}^{d-1}c_i p_{n+i}+\sum_{i=0}^{d-1}c_i q_{n+i}\\
&=\sum_{i=0}^{d-1}c_i (p_{n+i}+q_{n+i})
\end{align}</math>
임의의 상수 <math>c</math>에 대해
: <math>\begin{align}
cp_{n+d}&=c\sum_{i=0}^{d-1}c_i a_{n+i}\\
&=\sum_{i=0}^{d-1}c_i (ca_{n+i})
\end{align}</math>
따라서 <math>W</math>는 <math>V</math>의 [[부분공간]]이다.

이제 <math>W</math>의 [[차원]]을 구해보자. 선형연산자 <math>L:W\to W</math>를 다음과 같이 정의하자.
: <math>L(a_n)=(a_{n+1})</math>
그러면 <math>L</math>을 <math>k</math>번 합성한 선형연산자 <math>\underbrace{L\circ L\circ \cdots \circ L}_{k\text{ times}}</math>를 <math>L^k</math>라 하고 <math>L^0</math>을 항등변환이라 하면
: <math>L^k (a_n)=(a_{n+k})</math>
이다.
[[다항식]] <math>f(x)</math>를
: <math>f(x)=x^d-\sum_{i=0}^{d-1}c_i x^i</math>
로 정의할 때, 새로운 선형연산자 <math>f(L):W\to W</math>를
: <math>f(L)(a_n)=\left(L^d-\sum_{i=0}^{d-1}c_i L^i\right)(a_n)</math>
으로 정의하면
: <math>\begin{align}
f(L)(a_n)&=\left(L^d-\sum_{i=0}^{d-1}c_i L^i\right)(a_n)\\
&=L^d (a_n) -\sum_{i=0}^{d-1}c_i L_i(a_n)\\
&=(a_{n+d})-\sum_{i=0}^{d-1}c_i (a_{n+i})\\
&=\left(a_{n+d}-\sum_{i=0}^{d-1}c_i a_{n+i}\right)
\end{align}</math>
이므로 <math>f(L)(a_n)=(0)</math>일 필요충분조건은 <math>(a_n)</math>이 선형점화식을 만족하는 것이다. 따라서 <math>W=\ker f(L)</math>이다. 이제 함수 <math>g:\ker f(L)\to \mathbb{C}^d</math>를
: <math>g(a_n)=(a_0,a_1,\cdots,a_{d-1})</math>
로 정의하자. 그러면 수열공간의 정의에 의해 <math>g</math>는 명백한 선형사상이다. 이제 <math>g</math>가 [[위로의 함수]]임을 보이자. 임의의 <math>a_0,a_1,a_2,\cdots, a_{d-1}</math>에 대해
: <math>\begin{align}
a_d&=\sum_{i=0}^{d-1} c_i a_i\\
a_{d+1}&=\sum_{i=0}^{d-1} c_i a_{i+1}\\
a_{d+2}&=\sum_{i=0}^{d-1} c_i a_{i+2}\\
&\vdots
\end{align}</math>
이므로 수열 <math>(a_n)</math>이 귀납적으로 정의되어, <math>g</math>는 위로의 함수인 동시에 일대일 함수이고, 따라서 <math>g</math>는 일대일 대응이다. <math>g</math>가 선형사상인 동시에 일대일 대응이므로, <math>g</math>는 [[동형사상]]이며 <math>\ker f(L)</math>과 <math>\mathbb{C}^d</math>는 동형이다. 이때 <math>\dim \mathbb{C}^d =d</math>이므로, <math>\dim\ker f(L)=d</math>이다. 따라서 선형점화식이 주어졌을 때, 점화식을 만족하는 수열은 [[선형독립]]인 수열 <math>d</math>개의 [[일차결합]]으로 나타난다.

== 동차선형점화식의 풀이 ==
수열 <math>(a_n)</math>의 선형점화식에서 <math>f(n)=0</math>일 경우, 그 점화식은 동차선형점화식(homogeneous linear recurrence relation)이라고 한다. <math>f(n)\ne 0</math>이면 비동차선형점화식(nonhomogeneous linear recurrence relation)이라고 한다.
=== 차수가 2인 경우 ===
일반적인 등비수열의 점화식이
: <math>a_{n+1} = ra_n</math> (단, <math>r</math>은 상수)
로 주어졌을 경우, 일반항은
: <math>a_n=cr^n</math>
으로 주어진다. 이제 좀 더 복잡한 점화식
: <math>a_{n+2}=r_1 a_{n+1}+r_0 a_n</math>
을 생각하자. <math>a_n=t^n</math>이 점화식을 만족한다고 가정하고 위의 점화식에 대입하면
: <math>t^{n+2}=r_1t^{n+1}+r_0t^n</math>
을 얻고 식을 간단히 하여
: <math>t^2 - r_1 t -r_0=0</math>
을 얻는다. [[이차방정식]]의 근의 공식에 의해
: <math>t=\frac{r_1\pm \sqrt{r_1^2 + 4r_0}}{2}</math>
이다. <math>\alpha,\beta</math>를
: <math>\alpha=\frac{r_1+ \sqrt{r_1^2 + 4r_0}}{2},\beta=\frac{r_1- \sqrt{r_1^2 + 4r_0}}{2}</math>
로 정의하자. 그러면 <math>(\alpha^n)</math>와 <math>(\beta^n)</math>은 점화식을 만족하는 수열임을 안다. 그러면 임의의 상수 <math>C_1,C_2</math>에 대해 <math>(C_1\alpha^n + C_2 \beta^n)</math>은 <math>(a_n)</math>의 점화식을 만족한다.
==== <math>\alpha\ne\beta</math>일 때 ====
<math>\alpha\ne\beta</math>일 때, <math>(\alpha^n)</math>과 <math>(\beta^n)</math>이 선형독립임을 보이자. <math>x_1,x_2\in \mathbb{C}</math>에 대해,
: <math>x_1 (\alpha^n) + x_2 (\beta^n)=(0)</math>
가 성립한다고 하자. 그러면 임의의 자연수 <math>n</math>에 대해 <math>x_1 \alpha^n + x_2 \beta^n =0</math>인데, <math>n=0,1</math>을 대입하면
: <math>\begin{cases}
x_1 + x_2 &= 0\\
\alpha x_1 + \beta x_2 &= 0
\end{cases}</math>
에서 <math>x_1=x_2=0</math>을 얻는다. 따라서 <math>(\alpha^n)</math>과 <math>(\beta^n)</math>은 선형독립이므로, 선형점화식을 만족하는 임의의 수열의 일반항은 <math>a_n = C_1 \alpha^n + C_2 \beta^n</math> 꼴로 나타낼 수 있다.

이제 초기값으로 <math>a_0,a_1</math>이 정해졌다고 하자.
: <math>\begin{cases}
a_0 &= C_1 +C_2\\
a_1 &= C_1 \alpha+C_2\beta
\end{cases}</math>
이므로, [[연립방정식]]을 풀면
: <math>C_1=\frac{a_1-a_0\beta}{\alpha-\beta},C_2=\frac{a_0\alpha-a_1}{\alpha-\beta}</math>
로 <math>C_1,C_2</math>는 [[존재성과 유일성|유일하게 정해진다]].

점화식으로부터 수열의 일반항을 구할 때 [[선형대수학]]을 이용할 수도 있다. 수열의 항 <math>a_0,a_1,\cdots, a_{n+1}</math>에 대해
: <math>\begin{align}
\begin{bmatrix}
a_{n+1}\\
a_n
\end{bmatrix}
&=
\begin{bmatrix}
r_1 & r_0\\
1 & 0
\end{bmatrix}
\begin{bmatrix}
a_n\\
a_{n-1}
\end{bmatrix}\\
&=
\begin{bmatrix}
r_1 & r_0\\
1 & 0
\end{bmatrix}^n
\begin{bmatrix}
a_1\\
a_0
\end{bmatrix}
\end{align}</math>
이다. 한편 <math>\begin{bmatrix}
r_1 & r_0\\
1 & 0
\end{bmatrix}</math>의 고윳값을 <math>\lambda</math>라 하면
: <math>-\lambda(r_1-\lambda)-r_0=0</math>
에서
: <math>\lambda=\alpha\text{ or }\lambda=\beta</math>
를 얻는다. 만약 <math>\alpha \ne \beta</math>라면, <math>\begin{bmatrix}
r_1 & r_0\\
1 & 0
\end{bmatrix}</math>는 서로 다른 두 개의 [[고윳값]]을 가지므로 대각화 가능하다. 행 동치(row equivalent)인 2차 정사각행렬의 [[동치관계]]를 <math>\sim</math>라 하면
: <math>\begin{bmatrix}
r_1-\alpha & r_0\\
1 & -\alpha
\end{bmatrix}\sim\begin{bmatrix}
1&-\alpha\\
0&0
\end{bmatrix}</math>
이므로 <math>\lambda=\alpha</math>에 대응하는 고유벡터는 <math>\begin{bmatrix}
\alpha\\
1
\end{bmatrix}</math>이고, 똑같은 방법으로 <math>\lambda=\beta</math>에 대응하는 고유벡터는 <math>\begin{bmatrix}
\beta\\
1
\end{bmatrix}</math>
임을 안다. 따라서
: <math>\begin{bmatrix}
\alpha & \beta\\
1 & 1
\end{bmatrix}^{-1}
\begin{bmatrix}
r_1 & r_0\\
1 & 0
\end{bmatrix}
\begin{bmatrix}
\alpha & \beta\\
1 & 1
\end{bmatrix}=\begin{bmatrix}
\alpha & 0\\
0 & \beta
\end{bmatrix}</math>
이고,
: <math>\begin{bmatrix}
\alpha & \beta\\
1 & 1
\end{bmatrix}^{-1}
\begin{bmatrix}
r_1 & r_0\\
1 & 0
\end{bmatrix}^n
\begin{bmatrix}
\alpha & \beta\\
1 & 1
\end{bmatrix}=\begin{bmatrix}
\alpha & 0\\
0 & \beta
\end{bmatrix}^n=\begin{bmatrix}
\alpha^n & 0\\
0 & \beta^n
\end{bmatrix}</math>
이므로
: <math>\begin{align}
\begin{bmatrix}
r_1 & r_0\\
1 & 0
\end{bmatrix}^n
&=\begin{bmatrix}
\alpha & \beta\\
1 & 1
\end{bmatrix}
\begin{bmatrix}
\alpha^n & 0\\
0 & \beta^n
\end{bmatrix}
\begin{bmatrix}
\alpha & \beta\\
1 & 1
\end{bmatrix}^{-1}
\\
&=\frac{1}{\alpha-\beta}\begin{bmatrix}
\alpha^{n+1} & \beta^{n+1}\\
\alpha^n & \beta^n
\end{bmatrix}
\begin{bmatrix}
1 & -\beta\\
-1 & \alpha
\end{bmatrix}\\
&=\frac{1}{\alpha-\beta}\begin{bmatrix}
\alpha^{n+1}-\beta^{n+1} & -\alpha^{n+1}\beta+\alpha\beta^{n+1} \\
\alpha^n-\beta^n & -\alpha^n\beta + \alpha\beta^n
\end{bmatrix}
\end{align}</math>
이다. 이 식을 대입하면
: <math>\begin{bmatrix}
a_{n+1}\\
a_n
\end{bmatrix}=\frac{1}{\alpha-\beta}\begin{bmatrix}
\alpha^{n+1}-\beta^{n+1} & -\alpha^{n+1}\beta+\alpha\beta^{n+1} \\
\alpha^n-\beta^n & -\alpha^n\beta + \alpha\beta^n
\end{bmatrix}\begin{bmatrix}
a_1\\
a_0
\end{bmatrix}</math>
이므로
: <math>a_n =\frac{-\alpha^n\beta + \alpha\beta^n}{\alpha-\beta} a_0 + \frac{\alpha^n-\beta^n}{\alpha-\beta} a_1</math>
을 얻는다.

==== <math>\alpha=\beta</math>일 때 ====
그런데 위에서 <math>\alpha=\beta</math>이면 <math>C_1,C_2</math>는 유일하게 정해지지 않는다. 일단 복소함수 <math>f</math>를
: <math>f(z)=z^{n+2}-r_1 z^{n+1}-r_0 z^n</math>
으로 정의하면 <math>\alpha</math>는 방정식 <math>f(z)=0</math>의 중근이므로, <math>f'(z)=0</math>의 해이기도 하다. 이때
: <math>f'(z)=(n+2)z^{n+1}-(n+1)r_1 z^n - nr_0 z^{n-1}</math>
이므로
: <math>(n+2)\alpha^{n+1}-(n+1)r_1 \alpha^n - nr_0 \alpha^{n-1}=0</math>
이고, 양변에 <math>\alpha</math>를 곱하면
: <math>(n+2)\alpha^{n+2}-r_1(n+1)\alpha^{n+1}-r_0n\alpha^n = 0</math>
이다. 따라서 <math>n\alpha^n</math>은 <math>(a_n)</math>의 점화식을 만족한다. 따라서 임의의 상수 <math>C_1,C_2</math>에 대해 <math>(C_1 \alpha^n + C_2 n\alpha^n)</math>은 <math>(a_n)</math>의 점화식을 만족한다. <math>(a_n)</math>과 <math>(na_n)</math>이 선형독립임을 보이자. <math>x_1,x_2\in \mathbb{C}</math>에 대해
: <math>x_1 (\alpha^n)+x_2(n\alpha^n)=(0)</math>
이라고 하자. <math>n=0,1</math>을 대입하면
: <math>\begin{cases}
x_1 &=0\\
\alpha(x_1+x_2 n)&=0
\end{cases}</math>
이므로 <math>x_1=x_2=0</math>을 얻는다. 따라서 <math>(a_n)</math>과 <math>(na_n)</math>이 선형독립이므로, 점화식을 만족하는 임의의 수열의 일반항은 <math>a_n = C_1 \alpha^n + C_2 n\alpha^n</math> 꼴로 나타낼 수 있다.

초깃값으로 <math>a_0,a_1</math>이 주어졌을 때,
: <math>\begin{cases}
a_0&= C_1\\
a_1&= C_1\alpha+C_2\alpha
\end{cases}</math>
이므로 연립방정식을 풀면
: <math>C_1 = a_0, C_2=\frac{a_1-\alpha a_0}{\alpha}\quad (\alpha\ne 0)</math>
을 얻는다.

=== 일반적인 경우 ===
일반적으로, 동차선형점화식 <math>a_{n+d}=\sum_{i=0}^{d-1}c_i a_{n+i}</math>가 주어졌을 때, <math>d</math>차방정식
: <math>x^d-\sum_{i=0}^{d-1}c_i x^i=0</math>
를 특성방정식(characteristic equation)이라고 한다. 특성방정식의 근을 <math>x_1,x_2,\cdots,x_d</math>라 하자.임의의 상수 <math>C_1,C_2,\cdots, C_d</math>에 대해 <math>\sum_{i=1}^d C_i x_i^n</math>은 선형점화식을 만족한다. 이제 주어진 선형점화식을 만족하는 수열 <math>(a_n)</math>의 초깃값 <math>a_0,a_1,\cdots, a_{d-1}</math>이 주어졌다고 하자.  만약 <math>x_1,x_2,\cdots,x_d</math>가 모두 다르다면, 연립방정식
: <math>\begin{bmatrix}
1 & 1 & \cdots & 1\\
x_1 & x_2 & \cdots & x_d\\
\vdots & \vdots & \ddots & \vdots\\
x_1^d & x_2^d & \cdots & x_d^d
\end{bmatrix}
\begin{bmatrix}
C_1\\
C_2\\
\vdots\\
C_d
\end{bmatrix}=
\begin{bmatrix}
a_0\\
a_1\\
\vdots\\
a_{d-1}
\end{bmatrix}
</math>
이 주어졌을 때 [[방데르몽드 행렬]]의 성질에 의해 연립방정식의 해는 유일하고, 따라서 <math>C_1,C_2,\cdots, C_d</math>는 유일하게 주어진다.

이제 특성방정식이 중근을 가질 경우의 해에 대해서 알아보자. 어떤 특성방정식의 근이 <math>x_1,x_2,\cdots, x_q</math>이고 각각의 중복도가 <math>m_1,m_2,\cdots, m_q\;(m_1+m_2+\cdots+m_q=d)</math>라고 하자. 즉, 특성방정식이
: <math>\prod_{i=1}^q (x-x_i)^{m_i}=0</math>
와 같이 표현된다고 하자. 그러면 임의의 <math>j\;(1\le j \le q)</math>에 대해 <math>(x_j^n), (nx_j^n), \cdots, (n^{m_j-1}x_j^n)</math>은 선형점화식을 만족하는 수열이다. 따라서 수열의 일반항은
: <math>\sum_{i=1}^q \sum_{j=1}^{m_i} C_{i,j}n^{j-1} x_i^n</math>
으로 나타난다. 이때 <math>C_{i,j}</math>는 임의의 상수이다.

=== 예제 1 ===
* '''문제''': 수열 <math>(a_n)</math>의 점화식이 <math>a_{n+2}=a_{n+1}+a_n</math>이라고 하자. <math>a_0=0,a_1=1</math>일 때, <math>(a_n)</math>의 일반항을 구하시오.
{{숨기기|Solution|
그 유명한 피보나치 수열의 일반항을 구하는 문제이다. 점화식의 특성방정식은 <math>x^2-x-1=0</math>이고, 이 방정식의 해는 <math>x=\frac{1\pm \sqrt{5}}{2}</math>이다. 따라서 <math>a_n=\left(\frac{1+ \sqrt{5}}{2}\right)^n C_1 + \left(\frac{1- \sqrt{5}}{2}\right)^nC_2</math>이다. 초깃값을 대입하면
: <math>\begin{cases}
C_1+C_2&=0\\
\frac{1+ \sqrt{5}}{2}C_1+\frac{1- \sqrt{5}}{2}C_2&=1
\end{cases}</math>
이고 이 연립방정식을 풀면 <math>C_1=\frac{1}{\sqrt{5}}, C_2=-\frac{1}{\sqrt{5}}</math>을 얻는다. 따라서 <math>(a_n)</math>의 일반항은 <math>a_n=\frac{1}{\sqrt{5}}\left(\left(\frac{1+ \sqrt{5}}{2}\right)^n-\left(\frac{1- \sqrt{5}}{2}\right)^n\right)</math>이다.

피보나치 수열의 일반항을 구하는 다른 방법에 대해선 [[라플라스 변환#점화식의 일반항 계산]]을 참고하라.
}}

=== 예제 2 ===
* '''문제''': 수열 <math>(a_n)</math>의 점화식이 <math>a_{n+2}=2a_{n+1}-2a_n</math>이라고 하자. <math>a_0=2,a_1=1</math>일 때, <math>(a_n)</math>의 일반항을 구하시오.
{{숨기기|Solution|
점화식의 특성방정식은 <math>x^2-2x+2=0</math>이고, 이 방정식의 해는 <math>x=1\pm i</math>이다. 따라서 <math>a_n=(1+i)^n C_1 + (1-i)^n C_2</math>이다. 그런데 [[오일러의 공식]]에 의해 <math>1\pm i = \sqrt{2}e^{\pm \frac{i\pi}{4}}=\sqrt{2}\left(\cos \frac{\pi}{4}\pm i\sin \frac{\pi}{4}\right)</math>이므로 <math>a_n=(\sqrt{2})^n\left(\cos \frac{n\pi}{4}+ i\sin \frac{n\pi}{4}\right)C_1+(\sqrt{2})^n\left(\cos \frac{n\pi}{4}- i\sin \frac{n\pi}{4}\right)C_2</math>로 달리 나타낼 수 있고, 또 정리하면
: <math>a_n=(\sqrt{2})^n\left((C_1+C_2)\cos\frac{n\pi}{4}+i(C_1-C_2)\sin\frac{n\pi}{4} \right)</math>
이다. 초깃값 <math>a_0=2,a_1=1</math>을 대입하면,
: <math>\begin{cases}
C_1+C_2&=2\\
(C_1+C_2)+i(C_1-C_2)&=1
\end{cases}</math>
에서 <math>C_1+C_2=2,C_1-C_2=i</math>를 얻는다. 따라서 <math>(a_n)</math>의 일반항은 <math>a_n=(\sqrt{2})^n\left(2\cos \frac{n\pi}{4}-\sin\frac{n\pi}{4}\right)</math>이다.
}}

=== 예제 3 ===
* '''문제''': 수열 <math>(a_n)</math>의 점화식이 <math>a_{n+3}=7a_{n+2}-16a_{n+1}+12a_n</math>이라고 하자. <math>a_0=2,a_1=5,a_2=9</math>일 때, <math>(a_n)</math>의 일반항을 구하시오.
{{숨기기|Solution|
점화식의 특성방정식은 <math>x^3-7x^2+16x-12=0</math>이고, 이 방정식의 해는 <math>x=2</math> (중근) 또는 <math>x=3</math>이다. 따라서 <math>a_n=2^n C_1 + n\cdot 2^nC_2+3^nC_3</math>이다. 초깃값을 대입하면
: <math>\begin{cases}
C_1+C_3 &= 2\\
2C_1 + 2C_2 + 3C_3 &=5\\
4C_1 + 8C_2 + 9C_3 &=9
\end{cases}</math>
이고 연립방정식을 풀면 <math>C_1=2,C_2=-1,C_3=1</math>을 얻는다. (연립방정식의 풀이과정은 독자에게 맡긴다.) 따라서 <math>(a_n)</math>의 일반항은 <math>a_n= 2^{n+1}- n\cdot 2^n + 3^n</math>이다.
}}

== 비동차선형점화식의 풀이 ==
<math>(a_n)</math>의 점화식이
: <math>a_{n+d}=\sum_{i=0}^{d-1}c_i a_{n+i}+f(n)</math>
이고 <math>f(n)\ne 0</math>이라고 하자. 어떤 수열 <math>(p_n)</math>이 <math>(a_n)</math>의 점화식을 만족한다고 하자. 즉,
: <math>p_{n+d}=\sum_{i=0}^{d-1}c_i p_{n+i}+f(n)</math>
그러면
: <math>a_{n+d}-p_{n+d}=\sum_{i=0}^{d-1}c_i (a_{n+i}-p_{n+i})</math>
이고 이 식은 동차선형점화식이다. 따라서 <math>\{(\alpha_{1,n}),(\alpha_{2,n}),\cdots,(\alpha_{d,n})\}</math>를 점화식
: <math>a_{n+d}=\sum_{i=0}^{d-1}c_i a_{n+i}</math>
의 해집합의 [[기저]]라고 하면 상수 <math>C_1,C_2,\cdots, C_d</math>에 대해
: <math>a_n-p_n=\sum_{i=1}^{d}C_i \alpha_{i,n}</math>
이고 다시 쓰면
: <math>a_n=\sum_{i=1}^{d}C_i \alpha_{i,n}+p_n</math>
이다. 한편 수열 <math>(q_n)</math>도 <math>(a_n)</math>의 점화식을 만족하면
: <math>p_{n+d}-q_{n+d}=\sum_{i=0}^{d-1}c_i (p_{n+i}-q_{n+i})</math>
이므로 <math>(p_n-q_n)</math>도 <math>(\alpha_{1,n}),(\alpha_{2,n}),\cdots,(\alpha_{d,n})</math>의 선형결합이다.

=== 차수가 1인 경우 ===
선형점화식
: <math>a_{n+1}=ra_n + cs^n</math>
이 주어졌다고 하자. 이때 <math>c,s</math>는 상수이며 <math>s\ne 0</math>이다. 만약 <math>r\ne s</math>이면, 식을 다음과 같이 변형 가능하다.
: <math>a_{n+1}-\frac{c}{s-r} s^{n+1} =r\left(a_n - \frac{c}{s-r} s^n \right)</math>
따라서
: <math>a_n = C r^n + \frac{c}{s-r}s^n</math>
을 얻는다. 이때 <math>C</math>는 임의의 상수이다.

이제 <math>r=s</math>라 가정하자. 즉, <math>a_{n+1}=ra_n+cr^n</math>으로 가정하자. 그러면
: <math>a_{n+1}-(n+1)cr^n = r(a_n - ncr^{n-1})</math>
이므로
: <math>a_n=C r^n + ncr^{n-1}</math>
을 얻는다. 동차선형점화식 <math>a_{n+1}=ra_n</math>의 일반해가 <math>a_n = Cr^n</math>이고, <math>r\ne s</math>일 때 특수해는 <math>\frac{c}{s-r}s^n</math>, <math>r=s</math>일 때 특수해는 <math>ncr^{n-1}</math>이므로 예상한 결과를 얻는다.

선형점화식
: <math>a_{n+1}=ra_n+\sum_{i=0}^{k}c_i n^i</math>
이 주어졌다고 하자.

<math>f(n)</math>이 다항함수이므로, 특수해도 다항함수로 추측해보도록 하자. 즉,
: <math>a_n = \sum_{i=0}^k b_i n^i</math>
를 주어진 점화식에 대입해보자. 그러면
: <math>\sum_{i=0}^k b_i (n+1)^i = r\sum_{i=0}^k b_i n^i + \sum_{i=0}^k c_i n^i</math>
이고, [[이항정리]]에 의해
: <math>(n+1)^i = \sum_{j=0}^i \binom{i}{j}n^j</math>
이므로
: <math>\begin{align}
\sum_{i=0}^k b_i (n+1)^i &= \sum_{i=0}^k \sum_{j=0}^i b_i \binom{i}{j}n^j\\
&=b_0\binom{0}{0} n^0\\
&+b_1\left(\binom{1}{0}n^0+\binom{1}{1}n^1\right)\\
&+b_2\left(\binom{2}{0}n^0+\binom{2}{1}n^1+\binom{2}{2}n^2\right)\\
&+\cdots\\
&+b_k\left(\binom{k}{0}n^0+\binom{k}{1}n^1+\binom{k}{2}n^2+\cdots + \binom{k}{k}n^k\right)\\
&=\sum_{i=0}^k \sum_{j=i}^k b_j \binom{j}{i} n^i
\end{align}</math>
이다. 따라서 정리하면
: <math>\sum_{i=0}^k \left(\sum_{j=i}^k b_j \binom{j}{i}-rb_i -c_i \right) n^i =0</math>
이고 따라서 임의의 <math>i=0,1,2,\cdots,k</math>에 대해
: <math>\sum_{j=i}^k b_j \binom{j}{i}-rb_i -c_i =0</math>
이므로
: <math>b_i=\begin{cases}
\frac{c_k}{1-r},& i=k\\
\frac{1}{1-r}\left(c_i -\sum_{j=i+1}^k b_j \binom{j}{i}\right),& 0\le i \le k-1
\end{cases}</math>
이다.

=== 예제 1 ===
* '''문제''': 수열 <math>(a_n)</math>의 점화식이 <math>a_{n+2}=-3a_{n+1}+10a_n+24n^2+2n+3</math>이라고 하자. <math>a_0=-5, a_1=-17</math>일 때 <math>(a_n)</math>의 일반항을 구하시오.
{{숨기기|Solution|
동차선형점화식 <math>h_{n+2}=-3h_{n+1}+10h_n</math>의 특성방정식은 <math>x^2+3x-10=0</math>이고, 방정식의 해는 <math>x=2</math> 또는 <math>x=-5</math>이다. 따라서 <math>h_n=C_1 2^n +C_2 (-5)^n</math> (<math>C_1,C_2</math>는 상수)이다. <math>f(n)=24n^2+2n+3</math>이므로 <math>p_n=an^2+bn+c</math> (단, <math>a,b,c</math>는 상수)로 추측한다. 이 식을 <math>(a_n)</math>의 점화식에 대입하고 정리하면
: <math>(-6a-24)n^2+(10a-6b-2)n+7a+5b-6c-3=0</math>
이므로
: <math>\begin{cases}
-6a-24&=0\\
10a-6b-2&=0\\
7a+5b-6c-3&=0
\end{cases}</math>
이다. 이 연립방정식을 풀면 <math>a=-4,b=-7,c=-11</math>을 얻는다. 그러면 <math>a_n=h_n+p_n=C_1 2^n + C_2 (-5)^n -4n^2 -7n -11</math>이고, 초깃값 <math>a_0=-5, a_1=-17</math>을 대입하면
: <math>\begin{cases}
C_1+C_2-11&=-5\\
2C_1-5C_2-22&=-17
\end{cases}</math>
이고, 이 연립방정식을 풀면 <math>C_1=5,C_2=1</math>을 얻는다. 따라서 <math>(a_n)</math>의 일반항은 <math>a_n=5\cdot 2^n +(-5)^n -4n^2-7n-11</math>이다.
}}

=== 예제 2 ===
* '''문제''': 수열 <math>(a_n)</math>의 점화식이 <math>a_{n+2}=2a_{n+1}-a_n+2^n</math>이라고 하자. <math>a_0=2, a_1=6</math>일 때, <math>(a_n)</math>의 일반항을 구하시오.
{{숨기기|Solution|
동차선형점화식 <math>h_{n+2}=2h_{n+1}-h_n</math>의 특성방정식은 <math>x^2-2x+1=0</math>이고, 이 방정식의 해는 <math>x=1</math>이며 중근이다. 따라서 <math>h_n=C_1 +C_2 n</math>이다.
한편 <math>f(n)=2^n</math>이므로 <math>p_n= r\cdot 2^n+s</math>로 두면
: <math>r\cdot 2^{n+2}+s=2r\cdot 2^{n+1}+2s-r\cdot 2^n -s + 2^n</math>
이고 정리하면
: <math>2^n r =2^n</math>
이므로 <math>r=1</math>이다. 한편 <math>p_0=2^0+s=1+s=2</math>이므로 <math>s=1</math>이다. 따라서 <math>a_n=C_1 +C_2 n+2^n+1</math>인데, 초깃값  <math>a_0=2, a_1=6</math>를 대입하면
: <math>\begin{cases}
C_1+2=2\\
C_1+C_2+3=6
\end{cases}</math>
이므로 <math>C_1=0,C_2=3</math>을 얻는다. 따라서 <math>(a_n)</math>의 일반항은 <math>a_n=2^n + 3n +1</math>이다.
}}

== 연립선형점화식 ==

== 활용 ==
비단 선형점화식에만 해당하는 내용은 아니고 일반적인 점화식에 대해 모두 해당하는 내용이지만, 현실 세계에서 일어나는 현상의 대부분은 재귀적이기 때문에 점화식을 사용하여 그 성질을 연구할 수 있다.

생물학에서는 그 유명한 [[피보나치 수열]]이 (현실성은 떨어지지만) [[토끼]]의 개체수를 연구하는데 쓰였다고 알려져 있으며, 현대에 인구 성장을 연구하기 위해서 쓰이는 로지스틱 맵도 점화식의 일종. 컴퓨터 공학에선 점화식을 떼놓을 수가 없는데, 프로그래밍에서 줄창 쓰이는 재귀함수는 사실 전부 점화식이다. 인공지능에서 쓰이는 피드백 역시 전부 재귀함수. 특히 선형점화식은 경제학에서 빼놓을 수가 없다. 가장 단순한 예로, 매 달 은행 이자가 1%씩 붙는다면, 통장 잔액은 <math>x_{n+1}=1.01x_n</math>이라는 선형점화식으로 계산할 수 있다. 물론 실생활에서는 저것 보다는 훨씬 복잡하지만.

[[수학 경시대회]]에서도 점화식은 빼놓을 수가 없는데, 경우의 수를 구하는 많은 문제는 점화식을 세운 뒤에 일반항을 구하여 푸는 것이 보편적이다. 아래는 몇가지 예시와 그 점화식.
*10계단을 올라가는데, 한 번에 1계단 또는 2계단만 올라갈 수 있다. 이 때, 10계단을 올라가는 경우의 수는?
*:매우 유명한 문제. 2계단 전에 2계단을 한 번에 오르거나, 1계단 전에 1계단을 오르는 것의 두 가지 경우로 쪼갤 수 있으며, 점화식을 세우면 [[피보나치 수열]]과 똑같은 <math>x_{n+2}=x_{n+1}+x_n</math>이 된다.
*4명이 파티에 모자를 쓰고 왔는데, 돌아갈 때 4명 모두 자기의 것이 아닌 모자를 쓰고 갈 경우의 수는?
*:[[교란순열]]로 알려져 있는 유명한 문제. 점화식은 <math>D_{n+2}=\left(n-1\right)\left(D_{n+1}+D_n\right)</math>이다.
*수열 012를 포함하지 않는 <math>n</math>자리 3진법의 수 (첫째 자리에 0이 와도 된다)
*:경우의 수를 <math>x_n</math>이라 하자. 첫째 자리가 1이나 2라면 나머지 <math>n-1</math>자리에 012가 포함되지 않으면 되므로, 경우의 수는 <math>2x_{n-1}</math>. 첫째 자리가 0이라면 나머지 <math>n-1</math>자리에 012가 포함되지 않는 경우의 수에서 첫째 자리 바로 뒤 두 수가 12인 경우를 제외하면 되므로 경우의 수는 <math>x_{n-1}-x_{n-3}</math>. 따라서, 점화식은 <math>x_n=3x_{n-1}-x_{n-3}</math>이다.

== 같이 보기 ==
* [[미분방정식]]

== 외부 링크 ==
* [http://www.eecs.yorku.ca/course_archive/2008-09/S/1019/Website_files/21-linear-recurrences.pdf Solving Linear Recurrence Relations]. 2015년 12월 8일 확인.
* [http://math.colorado.edu/~sebo2151/notes/rec.pdf SOLUTION SETS OF RECURRENCE RELATIONS]. 2015년 12월 8일 확인.
* [http://mathcircle.berkeley.edu/BMC3/Bjorn1/Bjorn1.html Linear recursive sequences]. 2015년 12월 9일 확인.

[[분류:수학]]