구체 수학 - #2.2 합과 점화식

이번 절은 합의 값을 실제로 구하는 방법을 알아본다.

한 가지 방법은 합과 점화식 사이에 밀접한 관계가 있다는 점을 주목하는 것이다.

 

정말 오랜만에 책의 수식을 하나씩 짚어가며 따라 해 봤다.

간단한 이항 및 사칙연산(분수 포함)만 가능하면 논리적으로 따라가는 데는 전혀 문제가 없으나

중간중간에 사용되는 아이디어들(특정 변수로 묶고, 그걸 계산해서 풀고, 여기저기로 옮기는)은 혼자 하라면 못할 듯싶다.

 

레퍼토리 법에 따라서 간단한 n의 함수들을 새로운 변수에 대입해보면서 해가 간단해지는 상수 매개변수를 찾는다.

지난 절 중에 나왔던 하노이의 탑 점화식과

빠른 정렬(quicksort)의 점화식에 대해서도 다룬다.

시그마 기호까지 지우는 방법을 사용하는 건 처음 봤는데, 나중에도 한 번씩 써먹을 것 같다.

조화수(harmonic number)에 대해서도 나오며 H = 1 + 1/2 + 1/3 +... 1/n의 수를 의미한다.

 

생각보다 재밌다!

물론 시간 투자를 좀 더 하긴 해야 하지만(약 40분 정도?)

그래도 수식을 쭉 따라가 보면서 맞아가는 걸 보니 꽤 즐겁다.