1883년 프랑스 수학자 루카스(Lucas, E)는 하노이 탑이라고 불려지게 된 유명한 문제를 고안해 내었다. 이것은 세 개의 기둥에서 왼쪽 기둥에 놓인 크기가 다른 원판을 오른쪽 기둥으로 옮기는 것이다. 가운데 기둥을 이용할 수 있으나 원판은 한 번에 한 번씩만 옮겨야 하고, 절대로 작은 원판 위에 큰 원판을 올려놓을 수 없다. 이동 횟수가 가장 적은 방법을 찾으면서 9개의 원판을 모두 다른 기둥으로 옮겨놓는 게임이다. 원판을 몇 번을 옮겨야 모두 세 번째 기둥으로 옮길 수 있는지를 알아보자.

 T_n을 한 기둥 위에 놓여있는 n개의 원판을 다른 기둥으로 옮기는데 필요한 회수라고 하자. n개의 원판을 옮기려면 위쪽에 있는 (n-1)개의 원판을 모두 다른 막대로 옮긴 후에 맨 아래 원판을 빈 막대로 옮기고, 다시 그 위에 (n-1)개의 원판을 옮겨 놓으면, 된다.

곧, n개의 원판을 이동하는 방법을 다음과 같다(기둥의 순서를 A, B, C라 하자)

{A→B로 (n-1)개 이동}+{A→C로 1개 이동}+{B→C로 (n-1)개 이동}

n개의 원판을 옮기는데 필요한 회수와 n+1개의 원판을 옮기는데 필요한 회수 사이에는 다음과 같은 관계가 있음을 알 수 있다.

T_n+1 =T_n + 1 + T_n = 2T_n + 1

한 개의 원판을 옮기는데 필요한 회수는 1이므로 T₁ = 1이다.

따라서 이를 관계를 점화식으로 다음과 같이 나타낼 수 있다.

이 식은 하노이 탑 수열이라고 불리는 수열의 귀납적 정의이다. 하노이 탑 수열의 각 항은 다음과 같이 구할 수 있다.

이것으로 하노이 탑 수열의 일반항은 T_n = 2ⁿ - 1임을 추측할 수 있다.

이 일반항은 다음과 같이 구할 수도 있다.

 T_n+1 + 1 = 2T_n + 2 = 2(T_n + 1)

 S_n = T_n + 1 이라고 하면

 S_n+1 = 2S_n 가 되어

 S_n은 공비가 2이고 첫째 항이  S₁ = T₁ + 1 = 2  인 등비수열이 된다.

따라서

 S_n = 2·2^{n-1 =} 2ⁿ

  ∴ T_n = 2ⁿ - 1