점화식을 재귀함수와 대응시키기

뒤의 두 개의 항을 곱해 다음 항의 값을 구할 수 있는 수열을 재귀함수로 대응

 

뒤의 두 개의 항을 곱해 다음 항의 값을 구할 수 있는 피보나치 수열을 재귀함수로 대응

 

대응 순서는

1. 점화식을 구한다.

2. 좌변이 An 항이 되도록 n의 값을 대입한다.

3. 좌변이 An인 점화식은 f(n)으로 대응한다.

4. 점화식 축차대입을 위한 초기 항들을 대응한다.

5. 2번에 구한 식을 완성한다.