[이산수학]재귀 관계(Recurrence Relations)

전에 수열에 대한 내용을 다룰 때 formula에는 두 가지가 있다고 했다.

바로 재귀적(recursive) 공식과 명시된(explicit) 공식이 그것인데,

재귀 관계 (Recurrence Relation) 은 recursive를 explicit으로 변환하는 문제에 관한 내용이다.

recursive formula를 사용하려면 initial condition (초기 조건)이 꼭 있어야 하는데, 이 초기 조건과 공식을 이용해 어떤 열을 나타내는 게 바로 재귀 관계이다.

 

───────────────────────────────────

 

백트래킹 (backtracking)은 recurrence relation으로 정의된 sequence의

explicit formula를 찾기 위해 사용되는 기술로, 이전 항목의 정의로 대치함으로써 거꾸로 패턴을 찾아가는 것이다.

 

───────────────────────────────────

 

그러나 백트래킹으로 패턴을 찾지 못하는 경우가 있다.

만약 recurrence relation이 Homogeneous relation of degree k 인 경우에는

이차방정식을 푸는 방법으로 해결할 수 있다.