I need some help to solve a modification of the Tower of Hanoi problem found on a french forum.
The classic problem is described here.
This modification is called Gebrane's Hanoi problem (from the name of its inventor), the $n$ disks are numbered from top to bottom from $1$ to $n$ and are also placed on peg $A$, and the goal is to move all the disks to pegs $B$ and $C$ to form two towers: the tower on peg $B$ is formed with all the even-numbered disks and the one on peg $C$ is formed with all the odd ones (obviously).
The other rules are the same: each move consist in displacing an upper disk of a tower on top of another tower or on an empty peg, and no disk may be placed on a smaller one.
Let $HG(n)$ be the minimum number of moves to solve Gebrane's Hanoi problem.
Prove that: $$HG(n)=-\frac 1{21}\cos\left(\frac2 3n\pi\right)+\frac 1 7\sqrt 3\sin\left(\frac2 3n\pi\right)+\frac 5 7 2^n-\frac 2 3.$$
Best Answer
Let's rename pegs $B$ and $C$ as $B'$ and $C'$ where $B'$ is the peg where disc $n$ and all other discs with the same parity are destined to move, and $C'$ is where the discs of opposite parity are to go.
Let $n\ge3$.
We need to move disc $n$ to $B'$. First we need to move discs $1$ to $n-1$ to $C'$; this needs $2^{n-1}-1$ moves. After $2^{n-1}$ moves we have disc $n$ on $B'$ the remaining discs on $C'$ and $A$ empty.
Both discs $n-1$ and $n$ are where we want them. We need to move disc $n-2$ to $B'$. So we need to move discs $1$ to $n-3$ from $C'$ to $A$, which takes $2^{n-3}-1$ moves, then an extra move to get $n-2$ to $B'$. After $2^{n-1}+2^{n-3}$ moves, we have $n-2$ and $n$ on $B'$ and $n-1$ on $C'$, and the remaining discs on $A$.
We are back to the original puzzle but with $n$ replaced by $n-3$. Therefore $$HG(n)=HG(n-3)+2^{n-1}+2^{n-3}=HG(n-3)+\frac58 2^{n}.$$ Now solve this recurrence (the solution will have the form $a2^n+b+c\cos(2n\pi/3)+d\sin(2n\pi/3)$).