점화식이란 수열에서 이웃하는 두개의 항 사이에 성립하는 관계를 나타내는 관계식이다. 즉, 수열 { an }의 각 항 an 이 함수 f를 이용해서 f(an) = an+1 과 같이 귀납적으로 정의 될때 f를 수열 {an}의 점화식이라고 하며 또한 수열 {an}은 점화식 f로 정의 된다고 한다. 예) 하노이의 탑 유명한 하노이이탑 문제는 n개의 원판을 이동하는 회수를 수열 an으로 정의 하면 n개의 원판을 이동시키기 위해서는 그 위쪽 n-1개의 원판을 다른 막대로 이동한 후, 맨 아래쪽 원판을 이동하고 다시 n-1개의 원판을 이동해야 하므로 다음과 같은 점화식이 성립함을 알수 있다. f(n) = f(n-1) + 1 + f(n-1) = 2*f(n-1) + 1 = 2^n - 1 (단, f(1)=1) 예) 피보나치..