This is from one of the exercises in "Concrete Mathematics", and is something I'm doing privately, not homework.
This is a variant on the classic towers of Hanoi, where all moves must be made clockwise only. The recursive solution is to consider $Q_n$ to be the number of moves to move a tower size $n$ one step across (e.g. from start $\rightarrow$ end post), and $R_n$ to be the number of moves to move it two (e.g start $\rightarrow$ end $\rightarrow$ spare).
The recursive solution is (sorry about the formatting, just getting to grips with tex):
$Q_n = 0 \quad \text{if n = 0}$
$Q_n = 2R_{n-1} + 1\quad \text{if n > 0}$
$R_n = 0 \quad \text{if n = 0}$
$R_n = Q_n + Q_{n-1} + 1 \quad \text{if n > 0}$
How can I prove these? I presume an inductive proof is required but everything I've tried to do just gets garbled into a mess of further decreasing $n$ values.
Explaining why these work is simple enough: $Q_n$ can be explained by the fact that you need to move a stack of size $n-1$ two steps forward followed by the $n$ piece, followed by moving the $n-1$ stack two steps again onto the $n$ piece=> $Q_n = R_{n-1} + 1 + R_{n-1} = 2R_{n-1}+1$.
The wordy proof for $R_n$ is similar: It consists of moving $R_{n-1}$ then 1 followed by $Q_n$, 1 and $R_{n-1}$ which will end us up with
$R_n = 2R_{n-1}+1+Q_{n-1}+1 = Q_n+Q_{n-1}+1$
But these are all just words that don't form any real proof... I've gone over the leading chapter and looked up some resources on proof by induction, but doing it with a recursion with two components has put me for a spin (having forgotten a lot of the math studied in the past certainly isn't helping either). If someone could run me through a rigorous proof for $n > 0$ it would be much appreciated.
As an aside, any recommended learning resources on proof by induction would be appreciated as I'm still barely "getting it".