점화식 문서 원본 보기

{{위키데이터 속성 추적}}
[[수학]]에서 '''점화식'''(漸化式) 또는 '''재귀식'''(再歸式, {{llang|en|recurrence relation}})이란 [[수열]]에서 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식이다. 즉, 수열 <math>\{a_n\}</math> 의 각 항 <math>a_n</math> 이 함수 ''f''를 이용해서

:<math>a_{n+1} = f(a_n)</math>

처럼 귀납적으로 정해져 있을 때, '''함수 ''f''를 수열 <math>\{a_n\}</math> 의 점화식'''이라고 하며, 또한, 수열 <math>\{a_n\}</math> 은 점화식 ''f'' 로 정의된다고 한다.

점화식을 '''푼다'''는 것은 귀납적으로 주어진 수열 <math>\{a_n\}</math> 의 일반항 <math>a_n</math> 을 n 의 명시적인 식(explicit formula)으로 나타내는 것을 말한다.

== 인접 2항간 점화식 ==
수열{''a''<sub>''n''</sub>} 이 점화식에 의해서 정의되고 점화식이 변수가 하나인 함수 ''f''에 의해서

: ''a''<sub>''n''+1</sub> = ''f''(''a''<sub>''n''</sub>)

로 나타내지고 있을 때, 이 점화식은 인접 2항간의 점화식이라고 한다.

=== 인접 2항간 선형 점화식 ===
인접 2항간 점화식중 ''f'' 가 일차식

: ''a''<sub>''n''+1</sub> = ''p''(''n'') · ''a''<sub>''n''</sub> + ''q''(''n'') (''p'', ''q''는 ''n'' 의 함수)

일 때, [[선형성|선형]]이라고 한다.

==== 계수가 모두 상수인 경우 ====
계수 ''p'', ''q''가 상수인 2항간 점화식, 즉,

: ''a''<sub>''n''+1</sub> = ''p'' · ''a''<sub>''n''</sub> + ''q'' (p, q는 n 에 관계하지 않는 상수)

라면, 이 점화식은 다음과 같이 해서 등차수열 혹은 등비수열에 귀착되어 일반항 n 의 식으로 명시적으로 기술할 수 있다.：

''p'' = 1 일 때, 점화식은 ''a''<sub>''n''+1</sub> = ''a''<sub>''n''</sub> + ''q''
이며, 이것은 등차수열을 나타낸다.

''p'' ≠ 1 일 때, 점화식 ''a''<sub>''n''+1</sub> = ''p'' · ''a''<sub>''n''</sub> + ''q'' 의 특성방정식이라 불리는 ''x'' = ''px'' + ''q'' 의 근을 α 라고 하면, 점화식은
:''a''<sub>''n''+1</sub> - α = ''p'' (''a''<sub>''n''</sub> - α)
으로 변형할 수 있다. 이것은 일반항이 ''b''<sub>''n''</sub> = ''a''<sub>''n''</sub> - α 로 정의되는 수열{''b''<sub>''n''</sub>} 이 공비가 ''p'' 인 등비수열이 된다는 뜻이 되며, ''b''<sub>''n''</sub> 을 ''n'' 의 식으로 쓸 수 있다. 다시, ''a''<sub>''n''</sub> = ''b''<sub>''n''</sub> + α 이므로, 이것도 ''n'' 의 식으로 표현이 가능하다.

===== 예 : 하노이의 탑 =====
유명한 [[하노이의 탑]](Tower of Hanoi) 문제가 있다. <math>n</math> 개의 원판을 이동하는 회수를 수열 <math>a_n</math>으로 정의하자. <math>n</math> 개의 원판을 이동시키기 위해서는 그 위쪽 <math>n-1</math>개의 원판을 다른 막대로 이동한 후, 맨 아래쪽 원판을 이동하고 다시 <math>n-1</math>개의 원판을 이동해야 하므로 다음과 같은 점화식이 성립함을 알 수 있다.
:<math>a_n = 2a_{n-1} + 1</math>
선형 점화식이므로 간단하게 일반항이 <math>2^n -1</math>임을 알 수 있다.

===== 등차수열·등비수열의 점화식 =====
[[등차수열]]이나 [[등비수열]]은 인접 2항간 점화식의 매우 특수한 형태이며, 그 정의에 의해 매우 단순한 점화식을 가진다. 즉,

: ''a''<sub>''n''+1</sub> = ''a''<sub>''n''</sub> + ''d'' (d는 상수)

와 같이 된다. 이 등차수열의 점화식에서 상수 d가 공차(''공통적인 차이'')이다. 이 점화식을 풀면 일반항의 식은 ''a''<sub>''n''</sub> = ''a''<sub>1</sub> + (''n'' - 1)''d'' 이 된다. 마찬가지로

: ''a''<sub>''n''+1</sub> = ''r'' · ''a''<sub>''n''</sub> (r는 상수)

이 등비수열의ff,상수 r 이 공비(''공통적인 비율'')이다. 이 점화식을 풀면 ''a''<sub>''n''</sub> = ''r''<sup>''n''-1</sup> · ''a''<sub>1</sub> 이란 일반항을 얻을 수 있다.

==== 계수가 상수가 아닌 경우 ====
이러한 경우 적절한 변형을 통해 해결이 가능한 형태로 변형해주는 작업이 필요하다. 몇몇 특수한 경우에 풀이법이 잘 알려져 있다.

===== p(n) = 1 인 경우 =====
이 경우 계차수열(인접한 두 항의 차로 이루어진 수열)이 <math>q(n)</math>이라는 일반항을 알고 있는 상태가 된다. 따라서 그 합을 구하면 즉시 일반항을 알 수 있게 된다. 점화식에 1부터 n까지 차례로 대입하여 다음 식들을 구성한다.
:<math>a_2 - a_1 = q(1)</math>
:<math>a_3 - a_2 = q(2)</math>
:<math>\vdots</math>
:<math>a_{n} - a_{n-1} = q(n-1)</math>
이므로 변변 모두 더하면 다음과 같은 일반항을 구할 수 있다.
:<math>a_n = a_1 + \sum_{k=1}^{n-1} q(k)</math>

===== q(n) = 0 인 경우 =====
이 경우 <math>p(n) = 1</math>인 경우와 마찬가지로 점화식에 1부터 n까지 차례로 대입하여 변변 곱하면 다음과 같은 일반항을 구할 수 있다.
:<math>a_n = a_1 \prod_{k=1}^{n-1} p(k)</math>

===== p(n)만 상수인 경우 =====
:<math>a_{n+1} = p a_n + q(n)</math>
점화식이 위와 같은 경우 양변을 <math>p^{n+1}</math>으로 나누면 다음과 같이 식을 바꿀 수 있다.
:<math>\frac{a_{n+1}}{p^{n+1}} = \frac{a_n}{p^n} + \frac{q(n)}{p^{n+1}}</math>
그러면 일반항이 <math>\frac{a_n}{p^n}</math>인 수열은 p(n) = 1인 경우와 동일함을 확인할 수 있다. 계차수열 <math>\frac{q(n)}{p^{n+1}}</math>의 합을 이용하여 일반항을 구한다.

===== p(n) = (n+1)/n 인 경우 =====
:<math>n a_{n+1} = (n+1) a_n + q(n)</math>
점화식이 위와 같은 경우 양변을 <math>n(n+1)</math>으로 나누면 일반항이 <math>a_n / n</math>인 수열은 p(n) = 1인 경우와 동일함을 확인할 수 있다.

===== p(n) = n 인 경우 =====
:<math>a_{n+1} = n a_n + q(n)</math>
점화식이 위와 같은 경우 양변을 <math>n!</math>으로 나누면, 일반항이 <math>a_n / (n-1)!</math>인 수열은 p(n) = 1인 경우와 동일함을 확인할 수 있다.

== 인접 3항간 점화식 ==
수열 {''a''<sub>''n''</sub>} 이 점화식에 의해서 정해지며, 점화식이 2 변수 함수 ''f''에 의해서

: ''a''<sub>''n''+2</sub> = ''f''(''a''<sub>''n''+1</sub>, ''a''<sub>''n''</sub>)
로 표현될 때, 이 점화식은 인접3항간의 점화식이라고 한다.

=== 인접 3항간 선형 점화식 ===
인접 3항간 점화식 중 f 가 일차식
:<math>a_{n+2} = p(n) a_{n+1} + q(n) a_n + r(n)</math>（''p'', ''q'', ''r'' 은 ''n'' 의 함수）

일 경우 선형이라고 한다.

==== r(n) = 0 이고 계수가 모두 상수인 경우 ====
상수 계수 선형 인접 3항간 점화식이 다음과 같다고 하자.
:<math>a_{n+2} = p a_{n+1} + q a_n</math>（''p'', ''q''는 ''n''에 무관한 상수）
이 경우, 특성 방정식(characteristic equation) ''x''<sup>2</sup> = ''px'' + ''q'' 의 근을 이용해 풀 수 있다.

즉, 특성 방정식 <math>x^2 = px + q</math>의 두 해를 <math>\alpha, \beta</math>라고 하면, 일반항이 <math>a_n = C_1 \alpha^n + C_2 \beta^n</math>인 수열은 주어진 점화식을 만족하게 된다. 따라서 초항의 값에 따라 미정계수 <math>C_1, C_2</math>를 결정하면 된다.

[[이차 방정식]]의 두 해가 중근이 될 경우 일반항을 <math>a_n = C_1 \alpha^n + C_2 n \alpha^n</math>로 두면 마찬가지로 주어진 점화식을 만족하게 된다. 이는 마치 상수계수만을 가진 2계도 선형 제차 미분방정식의 풀이를 연상하게 한다. (본질적으로 동일한 매커니즘이다.)

===== 예 : 피보나치 수열 =====
[[피보나치 수]](Fibonacci numbers)의 경우 초기값 <math>F_1 = 1, F_2 = 1</math>과 다음과 같은 선형 인접 3항간 점화식으로 정의되어 있다.
:<math>F_n = F_{n-1} + F_{n-2}</math>
[[이차 방정식]] <math>x^2 = x + 1</math>의 두 해는 <math>\frac{1+\sqrt{5}}{2} , \frac{1-\sqrt{5}}{2}</math>이므로 초항의 값을 대입하면 다음과 같은 일반항을 얻는다.
:<math>F_n = \frac{1}{\sqrt{5}}\left\{\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right\}</math>

==== 계수가 상수가 아닌 경우 ====
계수가 상수가 아닌 경우에는 각각의 점화식에 따라 다양한 기법을 적용해야 한다. 양변을 적절한 수로 나누는 등의 시도를 해 볼 수 있다.

===== 예 : 완전순열 =====
[[완전순열]] 혹은 교란순열([[:en:Derangement|Derangement]])이라 불리는 수열의 점화식은 다음과 같다.
:<math>d_n = (n-1)(d_{n-1} + d_{n-2})</math>
이 식은 다음과 같이 변형된다.
:<math>d_n - n d_{n-1} = -\{d_{n-1} - (n-1)d_{n-2}\}</math>
그러므로 <math>d_n - n d_{n-1}</math>을 새로운 수열 <math>a_n</math>으로 정의하면, 다음과 같은 점화식이 된다.
:<math>a_n = -a_{n-1}</math>
<math>a_n</math>의 일반항은 즉시 나오므로 다음과 같이 인접 3항간 점화식이 인접 2항간 점화식으로 변형된다.
:<math>d_n = n d_{n-1} + (-1)^n</math>
이 경우 위에서 다룬 인접 2항간 점화식에서 p(n) = n인 꼴이 된다. 양변을 <math>n!</math>으로 나누면, 일반항이 <math>d_n / (n-1)!</math>인 수열의 일반항을 알 수 있고 이로써 <math>d_n</math>의 일반항도 쉽게 유도된다.

===== p = - q - 1의 형태인 경우 =====
p = - q - 1인 경우는 특성방정식을 푸는 번거로운 과정없이 쉽게 답을 구할 수 있다. 점화식은 다음과 같이 변형된다.
:<math>a_{n+2} - a_{n+1} = - q(a_{n+1} - a_n)</math>
그러므로 그 계차수열이 공비가 - q 인 등비수열임을 확인할 수 있다. 계차수열의 일반항을 구해 그것으로부터 즉시 <math>a_n</math>의 일반항을 이끌어낼 수 있다.

== 상수계수의 선형 점화식 ==
점화식의 계수가 모두 상수인 선형 점화식
:<math>a_n = c_1a_{n-1} + c_2a_{n-2}+\cdots+c_da_{n-d}</math>
의 경우 다음과 같은 특성 방정식의 해를 구하여 일반항을 구한다.
:<math>x^d = c_1 x^{d-1} + \cdots + c_{d-1}x^1 + c_d</math>

=== 선형대수학을 이용한 해법 ===
다항 방정식을 이용한 풀이법도 있지만 [[선형대수학]]을 이용할 수도 있다. 다음과 같이 수열의 초기항을 [[고유벡터|고유기저]](eigenbasis)로 표현했다고 하자.
:<math>\begin{bmatrix}a_0\\
\vdots\\
a_{d-1}\end{bmatrix} = b_1v_1 + \cdots + b_dv_d</math>
이 경우 [[조르당 표준형]](Jordan normal form)을 이용하여 일반항을 구할 수 있다.
:<math>\begin{bmatrix}a_n\\
\vdots\\
a_{n+(d-1)}\end{bmatrix}
= C^n\begin{bmatrix}a_0\\
\vdots\\
a_{d-1}\end{bmatrix}
= C^n(b_1v_1 + \cdots + b_dv_d)
= \lambda_1^nb_1v_1 + \cdots + \lambda_d^n b_dv_d</math>
만약 행렬이 대각화(diagonalizable)되지 않으면 해법은 좀 더 복잡하게 된다.

==== 예 : 피보나치 수의 선형대수학을 이용한 해법 ====
[[피보나치 수]]의 점화식을 행렬로 표현하면 다음과 같이 된다.
:<math>\begin{bmatrix}F_{n+1}\\
F_n\end{bmatrix} = \begin{bmatrix}1&1\\
1&0\end{bmatrix} \begin{bmatrix}F_{n}\\
F_{n-1}\end{bmatrix}</math>
그러므로 일반항은 다음과 같이 된다.
:<math>\begin{bmatrix}F_{n+1}\\
F_n\end{bmatrix} = \begin{bmatrix}1&1\\
1&0\end{bmatrix}^{n-1} \begin{bmatrix}F_{2}\\
F_{1}\end{bmatrix}</math>
이 행렬은 다음과 같이 대각화 된다. 특성방정식의 <math>x^2 - x - 1 =0</math>의 두 해를 <math>\alpha, \beta</math>라고 두면, 이 두 값이 [[고윳값]]이므로
:<math>\begin{bmatrix}1&1\\
1&0\end{bmatrix} = \begin{bmatrix}\alpha & \beta\\
1&1\end{bmatrix}
\begin{bmatrix}\alpha & 0\\
0&\beta\end{bmatrix}
\begin{bmatrix}\alpha & \beta\\
1&1\end{bmatrix}^{-1}</math>
그러므로 일반항은 다음과 같이 정리되며 다항방정식을 이용한 풀이와 동일한 일반항을 얻을 수 있다.
:<math>\begin{bmatrix}F_{n+1}\\
F_n\end{bmatrix} = \begin{bmatrix}1&1\\
1&0\end{bmatrix}^{n-1} \begin{bmatrix}F_{2}\\
F_{1}\end{bmatrix} = \begin{bmatrix}\alpha & \beta\\
1&1\end{bmatrix}
\begin{bmatrix}\alpha^{n-1} & 0\\
0&\beta^{n-1}\end{bmatrix}
\begin{bmatrix}\alpha & \beta\\
1&1\end{bmatrix}^{-1} \begin{bmatrix}F_{2}\\
F_{1}\end{bmatrix}</math>

=== Z 변환을 이용한 해법 ===
[[Z변환|Z 변환]] 페이지 참조.

=== 수열의 합을 포함하는 경우 ===
점화식 내에 그 수열의 합이 들어있는 경우, 적절한 변형을 하여 인접한 몇 개의 항을 포함하는 점화식으로 바꾸어 준다. 예를 들어,
:<math>a_1 + a_2 + a_3 + \cdots + a_n = f(n)a_n</math>
점화식이 위와 같이 주어진 경우, 다음과 같이 인접 2항간의 점화식으로 변형한다.
:<math>f(n-1)a_{n-1} + a_n = f(n)a_n</math>
수열 <math>\{a_n\}</math>의 <math>n</math>째 항까지의 총합이 <math>S_n</math>인 경우, <math>S_n - S_{n-1} = a_n</math>임을 활용하여 인접 2항간의 점화식으로 변형가능한 것도 있다.

== 몇몇 간단한 비선형의 경우 ==
비선형의 경우 일반적인 풀이법은 없다. 그러나 몇몇 간단하게 해결되는 경우가 알려져 있다.

=== 예1 : 역수에 주목 ===
:<math>p a_n a_{n+1} = q a_n - r a_{n+1}</math>
점화식이 위와 같이 주어진 경우 양변을 <math>a_n a_{n+1}</math>으로 나누면 수열 {1/<math>a_n</math>}이 선형 점화식이 됨을 알 수 있다. 이 선형 점화식의 일반항을 구하여 해결한다.

=== 예2 : 로그를 취하여 해결가능한 경우 ===
:<math>a_{n+1} = 4a_n^2</math>
점화식이 위와 같이 주어진 경우 양변에 밑이 2인 로그를 취하면 <math>\log_2 a_{n+1} = 2 \log_2 a_n + 2</math>와 같이 변형되어 수열 <math>\{\log a_n\}</math>이 선형 점화식을 가짐을 알 수 있다. 따라서 선형 점화식을 풀면 쉽게 해결할 수 있다.

=== 예3 : 점화식의 역수를 취해 해결가능한 경우 ===
:<math>a_{n+1} = \frac{2a_n}{a_n + 2}</math>
점화식이 위와 같이 주어진 경우 양변의 역수를 취하면 수열 {1/<math>a_n</math>}이 선형 점화식을 가짐을 알 수 있다. 이 점화식을 풀면 쉽게 일반항을 구할 수 있다.

=== 예4 : 십진법에 기초한 점화식 ===
십진법에 기초하여 정의된 수열의 경우 쉽게 일반항을 구할 수 있는 경우가 있다. 예를 들어, 4가 이전의 항에서 하나씩 늘어가는 방법으로 정의된 수열이 있다고 하자. 즉,
:4, 44, 444, 4444, 44444, .....
이 경우 일반항은 다음과 같다.
:<math>\frac{4}{9}(10^n - 1)</math>
기수법이 다른 경우도 마찬가지 방법을 쓸 수 있다.

=== 예5 : 주기형의 경우 ===
:<math>a_{n+1} = - \frac{1}{a_n + 1}, \;a_n \ne -1</math>
점화식이 위와 같이 주어진 경우, n에 대한 식으로 표현하기 어렵다. 그러나 몇몇 값을 대입해보면 이 수열은 주기적으로 같은 값이 반복됨을 알 수 있다. 즉, <math>a, -\frac{1}{a+1}, -\frac{a+1}{a}</math> 이 세 수가 반복되어 나타난다.


== 생성함수를 이용한 해법 ==
[[생성함수 (수학)|생성함수]](generating function)를 이용하여 수열의 일반항을 찾는 것이 가능한 경우가 있다.

=== 예 1 ===
<math>a_1 = 0</math>이고 점화식이 아래와 같이 주어진 수열을 생각해보자.
:<math>a_{n+1} = 2a_n + 1</math>
이 수열을 계수로 갖는 다항식 <math>A(x) = \sum_{n=1}^{\infty} a_n x^n</math>은 다음 등식을 만족해야 한다.
:<math>\frac{A(x)}{x} = 2A(x) + \sum_{n=1}^{\infty} x^n = 2A(x) + \frac{x}{1-x}</math>
그러므로 <math>A(x)</math>를 구할 수 있고 이를 다시 [[부분분수]]로 분해하여 무한급수로 표현한다.
:<math>A(x) = \frac{x^2}{(1-x)(1-2x)} ={x} \left(\frac{1}{1-2x} - \frac{1}{1-x}\right) = \sum (2^{n-1} -1)x^n</math>

=== 예 2 ===
<math>a_0 = 1</math>이고 점화식이 아래와 같이 주어진 수열을 생각해보자.
:<math>a_{n+1} = 2a_n + n</math>
그런데 <math>\frac{d}{dx}\sum x^n = \sum nx^{n-1}</math>이라는 사실을 이용하여 <math>\sum nx^{n-1} = \frac{d}{dx}\frac{1}{1-x} = \frac{1}{(1-x)^2}</math>임을 알 수 있으므로, 이 수열을 계수로 갖는 다항식 <math>A(x)</math>은 다음 등식을 만족해야 함을 알 수 있다.
:<math>\frac{A(x)-1}{x} = 2A(x) + \frac{x}{(1-x)^2}</math>
마찬가지로 [[부분분수]]로 분해하여 무한급수로 표현한다.
:<math>A(x) = \frac{1-2x+2x^2}{(1-x)^2 (1-2x)} = \frac{-1}{(1-x)^2} + \frac{2}{1-2x} = \sum (2^{n+1} -n -1)x^n</math>

=== 예 3 : 피보나치 수열의 생성함수를 이용한 해법 ===
<math>n</math>번째 [[피보나치 수]]를 계수로 갖는 다항식 <math>F(x)</math>는 정의에 의해 다음을 만족해야 함을 즉시 알 수 있다.
:<math>\frac{F(x)-x}{x} = F(x) + xF(x)</math>
그러므로 다음을 얻는다.
:<math>F(x) = \frac{x}{1-x-x^2}</math>
방정식 <math>1-x-x^2 =0</math>의 두 근을 <math>r_1 , r_2</math>라고 하면 다음과 같이 [[부분분수]]로 분해된다.
:<math>F(x) = \frac{1}{r_1 - r_2} \left(\frac{1}{1-xr_1} - \frac{1}{1-xr_2}\right)</math>
이것을 무한급수로 표현하면 일반항을 얻을 수 있다.

== 같이 보기 ==
{{위키배움터|점화식 예제|점화식 예제}}
* [[미분 방정식]]

== 참고 ==
* [http://www.ktword.co.kr/abbr_view.php?m_temp1=1364 정보통신기술용어해설]
* [http://mathworld.wolfram.com/Difference-DifferentialEquation.html 매스월드]

{{전거 통제}}

[[분류:점화식| ]]
[[분류:재귀]]
[[분류:대수학]]