河內塔是有國數學家愛德華·盧卡斯於1883發明的．給定壹個由8個圓盤組成的塔，這些圓盤按照大小遞減的方式套在三根樁柱中的壹根上．
我們先以最少的大小兩個圓盤來說
T 0 =0
T n =2T n-1 +1
正常的遞歸公式已經完成。我們可以進壹步進行公式演算(數學歸納法)
T 0 +1=1
T n +1=2T n-1 +2
如果令U n =T n +1,那麽就有
U n =2U n-1 =>U n =2 n
如是推導出