This problem arrives from the Tower of Hanoi problem. We know that the least number of moves required to move the tower from one point to another is $2^n- 1$ where $n$ is the number of discs in the tower. I'm trying to use the recursive function associated with this problem to generate this closed formula. However, I'm not sure how to design the matrix.
The recursive function is: $M_n = 2M_{n-1} + 1$, where $M_a$ is the minimum number of moves needed for a tower with $a$ discs.
Any suggestions how to construct this matrix would be appreciated.
When all is done, I should have:
$A^nb = c$ Where $A$ is the 2x2 matrix, $b$ is the 2x1 vector of $M_1 (=1)$ and $M_2$ (=3), $n$ is the number of discs, and $c$ is the 2x1 vector showing $M_n$ and $M_{n+1}$.
Because of the constant term in the recursion relation and because $M_{n+1}$ only depends on $M_n$ but not $M_{n-1}$, our matrix will not be quite as you explained. Instead, we will use vectors of the form $\left(\begin{matrix} M_n \\ 1\end{matrix}\right)$.
We are thus seeking for a matrix $A = \left(\begin{matrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{matrix}\right)$ such that $$\left(\begin{matrix} M_{n+1} \\ 1 \end{matrix}\right) = A\left(\begin{matrix} M_{n} \\ 1 \end{matrix}\right)$$ holds. The two equations this matrix represents are $$M_{n+1} = a_{11} M_{n} + a_{12}$$ and $$1 = a_{21} M_{n} + a_{22}.$$ To make the first equation true, we use the recursion relation and choose $a_{11} = 2$, $a_{12} = 1$. The second equation becomes true if we choose $a_{21} = 0$ and $a_{22} = 1$. Thus our matrix is $$A = \left(\begin{matrix} 2 & 1 \\ 0 & 1 \end{matrix}\right)$$ and $$\left(\begin{matrix}M_{n+1} \\ 1 \end{matrix}\right) = A^n \left(\begin{matrix} M_1 \\ 1 \end{matrix}\right).$$