하노이의 탑의 각 원반을 교대로 흑백으로 칠한다. 같은 색의 원반이 서로 닿지 않게 옮긴다고 가정할 때, 원반의 수가 n일 경우 최소의 이동 횟수가 2^n + (-1) 인 것을 수학적 귀납법으로 증명하여라. 예를 들어, 다음과 같은 증명에는 '같은 색의 원반이 서로 닿지 않는' 부분에 대한 고려가 없기 때문에 오류가 존재한다.


 k=1일 때는 자명하므로 k>=2일때부터 생각한다.

 k=n-1일 때 성립한다고 가정한다면, 가정에 의해

 k=n일 때, 위의 n-1단을 옆으로 옮기고, n번째단을 빈 막대로 옮길 수 있다.

 

 위 과정을 반복하면 모든 원반을 조건을 만족시키면서 다른 막대로 옮길 수 있다.






 정말 잘 모르겠어서 도움을 구해봅니다.. 미천한 중생을 구원해주세요 ㅠ