구체수학과 koosaga님 블로그를 참고했습니다. 수학적 귀납법 정수 $n$에 관한 어떤 명제가 모든 $n\ge n_0$에 대해 참임을 증명하는 일반적인 방법이다. 이는 2가지 단계로 나뉜다. 기초(basis) 단계: $n_0$에 대한 증명 귀납(induction) 단계: $n_0,\cdots, n-1$에 대해 증명되었다는 가정 하에 $n>n_0$에 대해 증명 하노이탑 세 개의 탑에서 하노이탑 규칙에 따라 옮기는 최소 이동 횟수를 구하면 된다. 우선, 정의를 잘 하는 것이 중요하다. 책의 필자는 명명정복이라고 한다. $T_n:=$ 규칙 하에 다른 한 기둥으로 옮기는데 필요한 최소 이동 횟수 1번 기둥에서 2번 기둥으로 위쪽 $n-1$개의 원판을 옮기고, $n$번째 원판을 3번 기둥으로 옮긴 후 2번 기둥..