Solve X(n) = 2X(n-1) + 2 recurrence relation I'm trying to solve the excersice from Knuth's "Concrete
Mathematics":

A Double Tower of Hanoi contains 2n disks of n different sizes, two of
each size. As usual, we're required to move only one disk at a time, 
without putting a larger one over a smaller one.

How many moves does it take to transfer a double tower from one peg to
another, if disks of equal size are indistinguishable from each other?


My solution was like this. Let $n$ be the number of disks of
different sizes and $X_n$ - number of moves. The first few solutions
are:

$n = 0$ $X_n = 0$

$n = 1$ $X_n = 2$

$n = 2$ $X_n = 6$

$n = 3$ $X_n = 14$

Recurrence is $X_n = 2X_{n-1} + 2$

We can add $2$ to both sides:

$X_n+2 = 2X_{n-1} + 4$

let $Y_n = X_n + 2$, then

$Y_n = 2Y_{n-1}$

$Y_n = 2^n$

$X_n = 2^n - 2$

The problem is that the correct solution is $2^{n+1} - 2$, but I
cannot find an error in my approach.
Your $Y_0$ is probably wrong. $Y_0$ must be equal to $X_0+2=0+2=2$. Then $Y_n=2^{n+1}$ and hence $X_n=2^{n+1}-2$. Please double check.