점화식

틀:위키데이터 속성 추적 수학에서 점화식(漸化式) 또는 재귀식(再歸式, 틀:Llang)이란 수열에서 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식이다. 즉, 수열 $\{a_n\}$ 의 각 항 $a_n$ 이 함수 f를 이용해서

$a_{n+1}=f(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)$

$⋮$

$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(\frac{1+\sqrt{5}}{2}\right)}^n-{\left(\frac{1-\sqrt{5}}{2}\right)}^n\}$

계수가 상수가 아닌 경우

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

예 : 완전순열

완전순열 혹은 교란순열(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_1{a}_{n-1}+c_2{a}_{n-2}+\cdots +c_d{a}_{n-d}$

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

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

선형대수학을 이용한 해법

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

$\left[\begin{array}{c}{a}_0\\ ⋮\\ a_{d-1}\end{array}\right]=b_1{v}_1+\cdots +b_d{v}_d$

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

$\left[\begin{array}{c}{a}_n\\ ⋮\\ a_{n+(d-1)}\end{array}\right]=C^n\left[\begin{array}{c}{a}_0\\ ⋮\\ a_{d-1}\end{array}\right]=C^n(b_1{v}_1+\cdots +b_d{v}_d)={\lambda }_1^n{b}_1{v}_1+\cdots +{\lambda }_d^n{b}_d{v}_d$

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

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

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

$\left[\begin{array}{c}{F}_{n+1}\\ F_n\end{array}\right]=\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]\left[\begin{array}{c}{F}_n\\ F_{n-1}\end{array}\right]$

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

$\left[\begin{array}{c}{F}_{n+1}\\ F_n\end{array}\right]={\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^{n-1}\left[\begin{array}{c}{F}_2\\ F_1\end{array}\right]$

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

$\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]=\left[\begin{array}{cc}\alpha & \beta \\ 1& 1\end{array}\right]\left[\begin{array}{cc}\alpha & 0\\ 0& \beta \end{array}\right]{\left[\begin{array}{cc}\alpha & \beta \\ 1& 1\end{array}\right]}^{-1}$

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

$\left[\begin{array}{c}{F}_{n+1}\\ F_n\end{array}\right]={\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^{n-1}\left[\begin{array}{c}{F}_2\\ F_1\end{array}\right]=\left[\begin{array}{cc}\alpha & \beta \\ 1& 1\end{array}\right]\left[\begin{array}{cc}{\alpha }^{n-1}& 0\\ 0& {\beta }^{n-1}\end{array}\right]{\left[\begin{array}{cc}\alpha & \beta \\ 1& 1\end{array}\right]}^{-1}\left[\begin{array}{c}{F}_2\\ F_1\end{array}\right]$

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}^{\mathrm{\infty }}{a}_n{x}^n$은 다음 등식을 만족해야 한다.

$\frac{A(x)}{x}=2A(x)+\sum _{n=1}^{\mathrm{\infty }}{x}^n=2A(x)+\frac{x}{1-x}$

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

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

예 2

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

$a_{n+1}=2a_n+n$

그런데 $\frac{d}{dx}\sum x^n=\sum n{x}^{n-1}$이라는 사실을 이용하여 $\sum n{x}^{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}(\frac{1}{1-x{r}_1}-\frac{1}{1-x{r}_2})$

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

같이 보기

• 미분 방정식

참고

• 정보통신기술용어해설
• 매스월드