%The towers of Hanoi recurrence
%
%{\color{red} \begin{verbatim} > re := a(n) = 2*a(n-1) + 1; iv := a(1) = 1; \end{verbatim}}
%%
%\begin{center}
%{\color{blue} $ re := a(n) = 2 \, a(n-1)+1; $ \\ $ iv := a(1) = 1 $ }
%\end{center}
%%
%{\color{red} \begin{verbatim} > rsolve( {re,iv}, a(n) ); \end{verbatim} }
%%
%\begin{center} {\color{blue} $ 2^n-1 $ } \end{center}
%%

A second order recurrence

%
{\color{red} \begin{verbatim} > re := a(n) = 5*a(n-1) - 6*a(n-2); \end{verbatim} }
%
\begin{center}
{\color{blue} $ re := a(n) = 5\, a(n-1)-6\, a(n-2) $ }
\end{center}
%
{\color{red} \begin{verbatim} > rsolve( {re,a(0)=1,a(1)=4}, a(n) ); \end{verbatim} }
%
\begin{center} {\color{blue} $2\,{3}^{n}-{2}^{n}$} \end{center}

The mergesort recurrence

{\color{red} \begin{verbatim} > re := c(n) = 2*c(n/2) + n-1; \end{verbatim} }
%
\begin{center}
{ \color{blue} $ {\it re}\, := \,c \left( n \right) =2\,c \left( n/2 \right) +n-1 $ }
\end{center}
%
{\color{red} \begin{verbatim} > expand( rsolve( {re, c(1)=0}, c(n) ) ); \end{verbatim} }
%
\begin{center}
{\color{blue} $\displaystyle -n+{\frac {\ln  \left( n \right) n}{\ln  \left( 2 \right) }}+1$}
\end{center}

