세 막대를 차례로 A, B, C라 하고 현재 막대 A에 n 개의 원판이 놓여 있다고 하자.

이 원판을 모두 막대 B 또는 C로 옮기기 위해 원판을 옮기는 횟수를 f(n)이라 하자.

예를 들어 n=1 일 때는 그냥 한 번 옮기면 되므로 f(1) = 1 이다.

n=2일 때는 작은 원판을 B로 옮기고 큰 원판을 C로 옮기고 B에 있는 작은 원판을 C로 옮기면 된다.

따라서 f(2) = 3 이다.

자 이제 n개일 때를 생각해보자.

맨 위 원판에서 n-1번째 원판까지 n-1개의 원판을 B로 옮긴다. (이 횟수는 위 정의에 의하여 f(n-1) 이다.)

n번째 원판을 C로 옮긴다.

이제 B 에 있는 n-1개의 원판을 C로 옮긴다. (이 횟수도 f(n-1)이다.)

따라서 f(n) = 2f(n-1) + 1 이 성립한다.

이 관계식을 이용하면

f(1)=1, f(2)=3, f(3)=7, f(4)=15, ....

f(1)+1 = 2, f(2)+1 = 4, f(3)+1=8, f(4)+1=16, ...

수의 규칙이 보이나요?

따라서 f(n)+1 = 2^n 이므로 f(n) = 2^n - 1 입니다.

​