There are three towers named as **Left, Middle, Right.**

Tower Left contains 3 discs in decreasing size from bottom to top.

We have to move these 3 discs from Left tower to Right tower using Middle tower.

step 1: Move 2 discs from Left tower to Middle tower using Right tower. $n-1$ discs

Step 2: Move the remaining disc from Left tower to Right tower. $1-movement$

Step 3: Move 2 discs from Middle tower to Right tower using Left tower. $n-1$ discs

Recurrence relation:

$T(n) = T(n-1) + T(n-1) + 1$

$T(n) = 2T(n-1) + 1$