1. 점화식 (Recurrence Formula) / 점화관계 (Recurrence Relation) 이란?
ㅇ 수열의 각 항 간에 관계를, 간단하게 표현하는 관계식 (단순 나열이 아닌 규칙으로써)
- 수열의 n번째 항을, (일반항) ☞ 수열 용어 (수열, 점화식, 일반항 등) 참조
- 그 앞의 항들에 의해, (그보다 작은 항에 의해)
- 규칙적(종속적)으로 표현한 관계식 (자신 보다 작은 변수에 의한 함수로 표현)
2. 점화식 例
ㅇ 등차 수열 : an = an-1 + d
ㅇ 등비 수열 : an = a rn-1
ㅇ 피보나치 수열 : an = an-1 + an-2
ㅇ 계승(n!) 수열 : fn = n fn-1
ㅇ 하노이의 탑 : T1 = 1, Tn = 2Tn-1 + 1
- 일반항 : Tn = 2n -1
3. 점화식 특징
ㅇ 점화식의 구성 형태
- 등식 또는 관계식 형태를 갖춤
. 단, 문제 제시 때는, 초기값 또는 경계값이 반드시 필요
ㅇ 점화식이 주는 정보
- 점화식 자체는, 간접적이고 부분적인 정보 만 줌
- 따라서, 일반항을 구할 필요 있음
ㅇ 점화식을 풀기
- 수열의 일반항(general term)을 구하는 것
. 대부분, 수열의 초기값과 점화식을 이용하여 일반항(점화식 해)을 구할 수 있으나,
. 그러나, 수열의 일반항을 구할 수 없거나, 적절한 점화식으로 표현 못하는 경우도 많음
- 수열의 일반항을 구하는 일반화된 방법론은, => 생성 함수에 의함
ㅇ 점화식의 해(解) : 일반항
- 점화관계를 만족시키는 닫힌 형식의 수열 공식 (즉, 일반항)
ㅇ 점화식의 응용
- 주로, 수열의 재귀적 정의에 이용됨
4. 생성 함수 (Generating Function)
ㅇ 수열 { an } (n ≥ 0) 에 대한 생성 함수는 다음과 같이 정의 함
[# f(x) = a_0 + a_1x + a_2x^2 + \dots = \displaystyle\sum_{k=0}^{\infty} a_kx^k #]
ㅇ 수열의 정보(수열의 일반항, 크기 등)를 담고있는 급수 형태의 함수