하노이 탑을 점화식으로 생각해봅시다

도넛 블럭이 n개 있을 때 옮겨져야 되는 횟수를 a_n이라고 하겠습니다.

n+1개의 블럭이 있을 경우를 살펴봅시다.

맨 아래에 총 n+1개가 있는 상황입니다. 이제 다른 탑으로 최소가 되도록 도넛블럭들을 움직여야 합니다.

우리는 이 때 총 이동시키는 데 걸린 횟수를 a_n+1 이라고 할 수 있겠죠?

일단 먼저 n+1개를 다 옮기기 전에 n개를 먼저 옮겨야 n+1개를 움직일 수 있습니다.

그러므로 a-n만큼 이동시켜야 합니다.

그리고 남은 한개도 위치를 변경해야 하니까 1번 움직여 줘야 합니다.

그러므로 지금까지 블럭을 (a_n) + 1번 움직였죠?

2번째 탑에 있던 n개의 블럭을 오른쪽 위에 올려주어야 완성되겠죠? 그러니까 an번 더움직여야 합니다.

그럼 우리는 지금까지 2(a_n)+1 번 도넛을 총 움직였습니다.

결국 a_n+1 = 2(a_n) + 1이라는 점화식이 나오게 됩니다.

이제 이 점화식을 일반항으로 고치기 위해 등비수열 꼴을 만들어주겠습니다

(a_n+1) + 1=2(a_n) + 2

{(a_n+1)+1}=2{(a_n)+1}

결국 (a_n) +1이라는 수열은 등비 수열 꼴이죠? 이제 1부터 n-1까지의 수를 점화식에 대입에 축차대입 해볼게요

a_2 + 1 = 2(a_1 + 1)

a_3 + 1 = 2(a_2 + 1)

.

.

.

(a_n)+1=2{(a_n-1)+1}

이제 모든 식을 다 곱해버리면 중간 부분이 다 나뉘어버려 사라지고

(a_n)+1=2^(n-1)(a_1+1) 이라는 식만 남아버리죠!

a_1은 얼마겠어요. 블럭 한개를 다른 탑으로 옮기는 갯수니 1이겟죠?

(a_n)+1=2^(n-1)*2=2^n 이 되버리고 좌변항의 1을 이항시키면

a_n=2^n-1 이라는 일반항이 나옵니다.

결국 블럭이 n=1,2,3,4,5 . . . 일때 갯수를 공식을 통해 구할 수 있습니다.

1,3,7,15,31 이렇게 흘러가네요.