점화식
위키백과 ― 우리 모두의 백과사전.
점화식(漸化式)은 수열의 앞 뒤 항들끼리 만족하는 관계식이다. 좀 더 엄밀한 정의는 다음과 같다.
수열 {an} 의 각 항 an 이 함수 f 를 이용해서
- an+1 = f(a1, a2, ..., an)
처럼 귀납적으로 정해져 있을 때, 함수 f 를 수열 {an} 의 점화식이라고 하며, 또한, 수열 {an} 은 점화식 f 로 정의된다고 한다.
점화식을 푼다는 것은 점화식으로 주어진 수열 {an} 의 일반항 an 을 n 의 명시적인 식(explicit formula)으로 나타내는 것을 말한다.
[편집] 등차수열·등비수열의 점화식
등차 수열이나 등비수열은, 그 정의에 의해 매우 단순한 점화식을 가진다. 즉,
- an+1 = an + d (d 는 상수)
와 같이 된다. 이 등차수열의 점화식에서 상수 d가 공차(공통적인 차이)이다. 이 점화식을 풀면 일반항의 식은 an = a1 + (n - 1)d 이 된다. 마찬가지로
- an+1 = r · an (r 는 상수)
이 등비수열의 점화식이며,상수 r 이 공비(공통적인 비율)이다. 이 점화식을 풀면 an = rn-1 · a1 이란 일반항을 얻을 수 있다.
이들은 다음에 설명할 인접하는 2항간 점화식의 가장 단순한 것이다.
[편집] 인접2항간 점화식
수열 {an} 이 점화식에 의해서 정의되고 점화식이 변수가 하나인 함수 f 에 의해서
- an+1 = f(an)
로 나타내지고 있을 때, 이 점화식은 인접2항간의 점화식이라고 한다. 특히, f 가 일차식
- an+1 = p(n) · an + q(n)
(p, q 는 n 의 함수)
일 때, 선형이라고 한다. 계수 p, q가 상수인 2항간 점화식, 즉,
- an+1 = p · an + q
(p, q 는 n 에 관계하지 않는 상수)
라면, 이 점화식은 다음과 같이 해서 등차 수열 혹은 등비수열에 귀착되어 일반항 n 의 식으로 명시적으로 기술할 수 있다.：
p = 1 일 때, 점화식은 an+1 = an + q 이며, 이것은 등차수열을 나타낸다.
p ≠ 1 일 때, 점화식 an+1 = p · an + q 의 특성방정식이라 불리는 x = px + q 의 근을 α 라고 하면, 점화식은
- an+1 - α = p (an - α)
으로 변형할 수 있다. 이것은 일반항이 bn = an - α 로 정의되는 수열{bn} 이 공비가 p 인 등비수열이 된다는 뜻이 되며, bn 을 n 의 식으로 쓸 수 있다. 다시, an = bn + α 이므로, 이것도 n 의 식으로 표현이 가능하다.
[편집] 인접3항간 점화식
수열 {an} 이 점화식에 의해서 정해지며, 점화식이 2 변수 함수 f 에 의해서
- an+2 = f(an+1, an)
로 표현될 때, 이 점화식은 인접3항간의 점화식이라고 한다. 특히,f 가 일차식
- an+2 = p(n) · an+1 + q(n) · an
（p, q 는 n 의 함수）
일 경우 선형이라고 한다. 상수 계수 선형 인접3항간 점화식, 즉
- an+2 = p · an+1 + q · an
（p, q 는 n 에 무관한 상수） 라면, 특성 방정식 x2 = px + q 의 근을 이용해 풀 수 있다.
