사는 이야기/수학사전

점화식

후암동남산 2015. 3. 31. 13:47

점화식

수학에서 점화식(또는 재귀식)(Recurrence relation)이란 수열의 항 사이에서 성립하는 관계식을 말한다. 즉, 수열 { $a_n$ } 의 각 항 $a_n$ 이 함수 f 를 이용해서

a_{n+1} = f(a_1 , a_2 , .... , a_n )

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

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

인접 2항간 점화식[편집]

수열{a_n} 이 점화식에 의해서 정의되고 점화식이 변수가 하나인 함수 f 에 의해서

a_n+1 = f(a_n)

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

인접 2항간 선형 점화식[편집]

인접 2항간 점화식중 f 가 일차식

a_n+1 = p(n) · a_n + q(n) (p, q 는 n 의 함수)

일 때, 선형이라고 한다.

계수가 모두 상수인 경우[편집]

계수 p, q가 상수인 2항간 점화식, 즉,

a_n+1 = p · a_n + q (p, q 는 n 에 관계하지 않는 상수)

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

p = 1 일 때, 점화식은 a_n+1 = a_n + q 이며, 이것은 등차수열을 나타낸다.

p ≠ 1 일 때, 점화식 a_n+1 = p · a_n + q 의 특성방정식이라 불리는 x = px + q 의 근을 α 라고 하면, 점화식은

a_n+1 - α = p (a_n - α)

으로 변형할 수 있다. 이것은 일반항이 b_n = a_n - α 로 정의되는 수열{b_n} 이 공비가 p 인 등비수열이 된다는 뜻이 되며, b_n 을 n 의 식으로 쓸 수 있다. 다시, a_n = b_n + α 이므로, 이것도 n 의 식으로 표현이 가능하다.

예 : 하노이의 탑[편집]

유명한 하노이의 탑(Tower of Hanoi) 문제가 있다. $n$ 개의 원판을 이동하는 회수를 수열 $a_n$ 으로 정의하자. $n$ 개의 원판을 이동시키기 위해서는 그 위쪽 $n-1$ 개의 원판을 다른 막대로 이동한 후, 맨 아래쪽 원판을 이동하고 다시 $n-1$ 개의 원판을 이동해야 하므로 다음과 같은 점화식이 성립함을 알 수 있다.

a_n = 2a_{n-1} + 1

선형 점화식이므로 간단하게 일반항이 $2^n -1$ 임을 알 수 있다.

등차수열·등비수열의 점화식[편집]

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

a_n+1 = a_n + d (d 는 상수)

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

a_n+1 = r · a_n (r 는 상수)

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

계수가 상수가 아닌 경우[편집]

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

p(n) = 1 인 경우[편집]

이 경우 계차수열(인접한 두 항의 차로 이루어진 수열)이 $q(n)$ 이라는 일반항을 알고 있는 상태가 된다. 따라서 그 합을 구하면 즉시 일반항을 알 수 있게 된다. 점화식에 1 부터 n 까지 차례로 대입하여 다음 식들을 구성한다.

a_2 - a_1 = q(1)

a_3 - a_2 = q(2)

\vdots

a_{n} - a_{n-1} = q(n-1)

이므로 변변 모두 더하면 다음과 같은 일반항을 구할 수 있다.

a_n = a_1 + \sum_{k=1}^{n-1} q(k)

q(n) = 0 인 경우[편집]

이 경우 $p(n) = 1$ 인 경우와 마찬가지로 점화식에 1 부터 n 까지 차례로 대입하여 변변 곱하면 다음과 같은 일반항을 구할 수 있다.

a_n = a_1 \prod_{k=1}^{n-1} p(k)

p(n)만 상수인 경우[편집]

a_{n+1} = p a_n + q(n)

점화식이 위와 같은 경우 양변을 $p^{n+1}$ 으로 나누면 다음과 같이 식을 바꿀 수 있다.

\frac{a_{n+1}}{p^{n+1}} = \frac{a_n}{p^n} + \frac{q(n)}{p^{n+1}}

그러면 일반항이 $\frac{a_n}{p^n}$ 인 수열은 p(n) = 1인 경우와 동일함을 확인할 수 있다. 계차수열 $\frac{q(n)}{p^{n+1}}$ 의 합을 이용하여 일반항을 구한다.

p(n) = (n+1)/n 인 경우[편집]

n a_{n+1} = (n+1) a_n + q(n)

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

p(n) = n 인 경우[편집]

a_{n+1} = n a_n + q(n)

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

인접 3항간 점화식[편집]

수열 {a_n} 이 점화식에 의해서 정해지며, 점화식이 2 변수 함수 f 에 의해서

a_n+2 = f(a_n+1, a_n)

로 표현될 때, 이 점화식은 인접3항간의 점화식이라고 한다.

인접 3항간 선형 점화식[편집]

인접 3항간 점화식 중 f 가 일차식

a_{n+2} = p(n) a_{n+1} + q(n) a_n + r(n)

（p, q, r 은 n 의 함수）

일 경우 선형이라고 한다.

r(n) = 0 이고 계수가 모두 상수인 경우[편집]

상수 계수 선형 인접 3항간 점화식이 다음과 같다고 하자.

a_{n+2} = p a_{n+1} + q a_n

（p, q 는 n 에 무관한 상수）

이 경우, 특성 방정식(characteristic equation) x² = px + q 의 근을 이용해 풀 수 있다.

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

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

예 : 피보나치 수열[편집]

피보나치 수(Fibonacci numbers)의 경우 초기값 $F_1 = 1, F_2 = 1$ 과 다음과 같은 선형 인접 3항간 점화식으로 정의되어 있다.

F_n = F_{n-1} + F_{n-2}

이차 방정식 $x^2 = x + 1$ 의 두 해는 $\frac{1+\sqrt{5}}{2} , \frac{1-\sqrt{5}}{2}$ 이므로 초항의 값을 대입하면 다음과 같은 일반항을 얻는다.

F_n = \frac{1}{\sqrt{5}}\left\{\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right\}

계수가 상수가 아닌 경우[편집]

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

예 : 완전순열[편집]

완전순열 혹은 교란순열(Derangement)이라 불리는 수열의 점화식은 다음과 같다.

d_n = (n-1)(d_{n-1} + d_{n-2})

이 식은 다음과 같이 변형된다.

d_n - n d_{n-1} = -\{d_{n-1} - (n-1)d_{n-2}\}

그러므로 $d_n - n d_{n-1}$ 을 새로운 수열 $a_n$ 으로 정의하면, 다음과 같은 점화식이 된다.

a_n = -a_{n-1}

$a_n$ 의 일반항은 즉시 나오므로 다음과 같이 인접 3항간 점화식이 인접 2항간 점화식으로 변형된다.

d_n = n d_{n-1} + (-1)^n

이 경우 위에서 다룬 인접 2항간 점화식에서 p(n) = n인 꼴이 된다. 양변을 $n!$ 으로 나누면, 일반항이 $d_n / (n-1)!$ 인 수열의 일반항을 알 수 있고 이로써 $d_n$ 의 일반항도 쉽게 유도된다.

p = q - 1의 형태인 경우[편집]

p = q - 1인 경우는 특성방정식을 푸는 번거로운 과정없이 쉽게 답을 구할 수 있다. 점화식은 다음과 같이 변형된다.

a_{n+2} - a_{n+1} = q(a_{n+1} - a_n)

그러므로 그 계차수열이 공비가 q 인 등비수열임을 확인할 수 있다. 계차수열의 일반항을 구해 그것으로부터 즉시 $a_n$ 의 일반항을 이끌어낼 수 있다.

상수계수의 선형 점화식[편집]

점화식의 계수가 모두 상수인 선형 점화식

a_n = c_1a_{n-1} + c_2a_{n-2}+\cdots+c_da_{n-d}

의 경우 다음과 같은 특성 방정식의 해를 구하여 일반항을 구한다.

x^d = c_1 x^{d-1} + \cdots + c_{d-1}x^1 + c_d

선형대수학을 이용한 해법[편집]

다항 방정식을 이용한 풀이법도 있지만 선형대수학을 이용할 수도 있다. 다음과 같이 수열의 초기항을 고유기저(eigenbasis)로 표현했다고 하자.

\begin{bmatrix}a_0\\ \vdots\\ a_{d-1}\end{bmatrix} = b_1v_1 + \cdots + b_dv_d

이 경우 조르당 표준형(Jordan normal form)을 이용하여 일반항을 구할 수 있다.

\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

만약 행렬이 대각화(diagonalizable)되지 않으면 해법은 좀 더 복잡하게 된다.

예 : 피보나치 수의 선형대수학을 이용한 해법[편집]

피보나치 수의 점화식을 행렬로 표현하면 다음과 같이 된다.

\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}

그러므로 일반항은 다음과 같이 된다.

\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}

이 행렬은 다음과 같이 대각화 된다. 특성방정식의 $x^2 - x - 1 =0$ 의 두 해를 $\alpha, \beta$ 라고 두면, 이 두 값이 고윳값이므로

\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}

그러므로 일반항은 다음과 같이 정리되며 다항방정식을 이용한 풀이와 동일한 일반항을 얻을 수 있다.

\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}

Z 변환을 이용한 해법[편집]

Z 변환 페이지 참조.

수열의 합을 포함하는 경우[편집]

점화식 내에 그 수열의 합이 들어있는 경우, 적절한 변형을 하여 인접한 몇 개의 항을 포함하는 점화식으로 바꾸어 준다. 예를 들어,

a_1 + a_2 + a_3 + \cdots + a_n = f(n)a_n

점화식이 위와 같이 주어진 경우, 다음과 같이 인접 2항간의 점화식으로 변형한다.

f(n-1)a_{n-1} + a_n = f(n)a_n

수열 { $a_n$ }의 $n$ 째 항까지의 총합이 $S_n$ 인 경우, $S_n - S_{n-1} = a_n$ 임을 활용하여 인접 2항간의 점화식으로 변형가능한 것도 있다.

몇몇 간단한 비선형의 경우[편집]

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

예1 : 역수에 주목[편집]

p a_n a_{n+1} = q a_n - r a_{n+1}

점화식이 위와 같이 주어진 경우 양변을 $a_n a_{n+1}$ 으로 나누면 수열 {1/ $a_n$ }이 선형 점화식이 됨을 알 수 있다. 이 선형 점화식의 일반항을 구하여 해결한다.

예2 : 로그를 취하여 해결가능한 경우[편집]

a_{n+1} = 4a_n^2

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

예3 : 점화식의 역수를 취해 해결가능한 경우[편집]

a_{n+1} = \frac{2a_n}{a_n + 2}

점화식이 위와 같이 주어진 경우 양변의 역수를 취하면 수열 {1/ $a_n$ }이 선형 점화식을 가짐을 알 수 있다. 이 점화식을 풀면 쉽게 일반항을 구할 수 있다.

예4 : 십진법에 기초한 점화식[편집]

십진법에 기초하여 정의된 수열의 경우 쉽게 일반항을 구할 수 있는 경우가 있다. 예를 들어, 4가 이전의 항에서 하나씩 늘어가는 방법으로 정의된 수열이 있다고 하자. 즉,

4, 44, 444, 4444, 44444, .....

이 경우 일반항은 다음과 같다.

\frac{4}{9}(10^n - 1)

기수법이 다른 경우도 마찬가지 방법을 쓸 수 있다.

예5 : 주기형의 경우[편집]

a_{n+1} = - \frac{1}{a_n + 1}, \;a_n \ne -1

점화식이 위와 같이 주어진 경우, n에 대한 식으로 표현하기 어렵다. 그러나 몇몇 값을 대입해보면 이 수열은 주기적으로 같은 값이 반복됨을 알 수 있다. 즉, $a, -\frac{1}{a+1}, -\frac{a+1}{a}$ 이 세 수가 반복되어 나타난다.

생성함수를 이용한 해법[편집]

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

예 1[편집]

$a_1 = 0$ 이고 점화식이 아래와 같이 주어진 수열을 생각해보자.

a_{n+1} = 2a_n + 1

이 수열을 계수로 갖는 다항식 $A(x) = \sum_{n=1}^{\infty} a_n x^n$ 은 다음 등식을 만족해야 한다.

\frac{A(x)}{x} = 2A(x) + \sum_{n=1}^{\infty} x^n = 2A(x) + \frac{1}{1-x}

그러므로 $A(x)$ 를 구할 수 있고 이를 다시 부분분수로 분해하여 무한급수로 표현한다.

A(x) = \frac{x}{(1-x)(1-2x)} = \left(\frac{1}{1-2x} - \frac{1}{1-x}\right) = \sum (2^n -1)x^n

예 2[편집]

$a_0 = 1$ 이고 점화식이 아래와 같이 주어진 수열을 생각해보자.

a_{n+1} = 2a_n + n

그런데 $\frac{d}{dx}\sum x^n = \sum nx^{n-1}$ 이라는 사실을 이용하여 $\sum nx^{n-1} = \frac{d}{dx}\frac{1}{1-x} = \frac{1}{(1-x)^2}$ 임을 알 수 있으므로, 이 수열을 계수로 갖는 다항식 $A(x)$ 은 다음 등식을 만족해야 함을 알 수 있다.

\frac{A(x)-1}{x} = 2A(x) + \frac{x}{(1-x)^2}

마찬가지로 부분분수로 분해하여 무한급수로 표현한다.

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

예 3 : 피보나치 수열의 생성함수를 이용한 해법[편집]

$n$ 번째 피보나치 수를 계수로 갖는 다항식 $F(x)$ 는 정의에 의해 다음을 만족해야 함을 즉시 알 수 있다.

\frac{F(x)-x}{x} = F(x) + xF(x)

그러므로 다음을 얻는다.

F(x) = \frac{x}{1-x-x^2}

방정식 $1-x-x^2 =0$ 의 두 근을 $r_1 , r_2$ 라고 하면 다음과 같이 부분분수로 분해된다.

F(x) = \frac{1}{r_1 - r_2} \left(\frac{1}{1-xr_1} - \frac{1}{1-xr_2}\right)

이것을 무한급수로 표현하면 일반항을 얻을 수 있다.

'사는 이야기 > 수학사전' 카테고리의 다른 글

절대값, 가우스기호 해결방법 (0)	2015.05.16
* 절댓값 함수와 절댓값 그래프 특강(절대값 함수와 절대값 그래프 특강) (0)	2015.05.16
수열 (0)	2015.03.31
피보나치수열 (0)	2015.03.31
집합과 명제(1) (0)	2015.01.26

현재글점화식

남산과 함께하기

관찰자, 무신정권, 인식주체, 관악산, 주역, 형, 통찰자, 남산, 한퇴지, 인식대상,

Today :
Yesterday :

일	월	화	수	목	금	토
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30	31

남산과 함께하기

점화식

점화식

목차

인접 2항간 점화식[편집]

인접 2항간 선형 점화식[편집]

계수가 모두 상수인 경우[편집]

예 : 하노이의 탑[편집]

등차수열·등비수열의 점화식[편집]

계수가 상수가 아닌 경우[편집]

p(n) = 1 인 경우[편집]

q(n) = 0 인 경우[편집]

p(n)만 상수인 경우[편집]

p(n) = (n+1)/n 인 경우[편집]

p(n) = n 인 경우[편집]

인접 3항간 점화식[편집]

인접 3항간 선형 점화식[편집]

r(n) = 0 이고 계수가 모두 상수인 경우[편집]

예 : 피보나치 수열[편집]

계수가 상수가 아닌 경우[편집]

예 : 완전순열[편집]

p = q - 1의 형태인 경우[편집]

상수계수의 선형 점화식[편집]

선형대수학을 이용한 해법[편집]

예 : 피보나치 수의 선형대수학을 이용한 해법[편집]

Z 변환을 이용한 해법[편집]

수열의 합을 포함하는 경우[편집]

몇몇 간단한 비선형의 경우[편집]

예1 : 역수에 주목[편집]

예2 : 로그를 취하여 해결가능한 경우[편집]

예3 : 점화식의 역수를 취해 해결가능한 경우[편집]

예4 : 십진법에 기초한 점화식[편집]

예5 : 주기형의 경우[편집]

생성함수를 이용한 해법[편집]

예 1[편집]

예 2[편집]

예 3 : 피보나치 수열의 생성함수를 이용한 해법[편집]

'사는 이야기 > 수학사전' 카테고리의 다른 글

'사는 이야기/수학사전'의 다른글

티스토리툴바

점화식

점화식

목차

인접 2항간 점화식[편집]

인접 2항간 선형 점화식[편집]

계수가 모두 상수인 경우[편집]

예 : 하노이의 탑[편집]

등차수열·등비수열의 점화식[편집]

계수가 상수가 아닌 경우[편집]

p(n) = 1 인 경우[편집]

q(n) = 0 인 경우[편집]

p(n)만 상수인 경우[편집]

p(n) = (n+1)/n 인 경우[편집]

p(n) = n 인 경우[편집]

인접 3항간 점화식[편집]

인접 3항간 선형 점화식[편집]

r(n) = 0 이고 계수가 모두 상수인 경우[편집]

예 : 피보나치 수열[편집]

계수가 상수가 아닌 경우[편집]

예 : 완전순열[편집]

p = q - 1의 형태인 경우[편집]

상수계수의 선형 점화식[편집]

선형대수학을 이용한 해법[편집]

예 : 피보나치 수의 선형대수학을 이용한 해법[편집]

Z 변환을 이용한 해법[편집]

수열의 합을 포함하는 경우[편집]

몇몇 간단한 비선형의 경우[편집]

예1 : 역수에 주목[편집]

예2 : 로그를 취하여 해결가능한 경우[편집]

예3 : 점화식의 역수를 취해 해결가능한 경우[편집]

예4 : 십진법에 기초한 점화식[편집]

예5 : 주기형의 경우[편집]

생성함수를 이용한 해법[편집]

예 1[편집]

예 2[편집]

예 3 : 피보나치 수열의 생성함수를 이용한 해법[편집]

'사는 이야기 > 수학사전' 카테고리의 다른 글

'사는 이야기/수학사전'의 다른글

관련글

티스토리툴바