analysis algorithm - recurrence equation (tower of hanoi)

Question

I saw this recursive algorithm to solve the Tower of Hanoi in wikipedia. Could someone explain to me how I get the recurrence equation of this algorithm?

Recursive solution

• label the pegs A, B, C — these labels may move at different steps
• let n be the total number of discs
• number the discs from 1 (smallest, topmost) to n (largest, bottommost)

To move n discs from peg A to peg C:

• move n−1 discs from A to B. This leaves disc n alone on peg A
• move disc n from A to C
• move n−1 discs from B to C so they sit on disc n

The above is a recursive algorithm, to carry out steps 1 and 3, apply the same algorithm again for n−1. The entire procedure is a finite number of steps, since at some point the algorithm will be required for n = 1. This step, moving a single disc from peg A to peg B, is trivial.

Answer 1

First three steps can be done in a linear time, the second three steps are the recursive part, then, just simply write in recursive format what is written in plain text format:

T(n,A,C) = T(n-1,A,B) + 1 + T(n-1,B,C).

On the other hand, because labels are not important and T(n,A,B) = T(n,B,C)=T(n,A,C)=..., we can get rid of labels, so the equation will be ?