Using Henry’s notation, the system of recurrences is
$$\left\{\begin{align*}
&m_{AC}(n+1)=2m_{AC}(n)+m_{CA}(n)+2\\
&m_{CA}(n+1)=m_{CB}(n)+m_{BA}(n)+1\\
&m_{AB}(n+1)=m_{AC}(n)+m_{CB}(n)+1\\
&m_{BA}(n+1)=m_{BC}(n)+m_{CA}(n)+1\\
&m_{BC}(n+1)=m_{BA}(n)+m_{AC}(n)+1\\
&m_{CB}(n+1)=m_{CA}(n)+m_{AB}(n)+1\;.
\end{align*}\right.$$
Then $$\begin{align*}
m_{CA}(n+1)&=m_{CB}(n)+m_{BA}(n)+1\\
&=2m_{CA}(n-1)+m_{AB}(n-1)+m_{BC}(n-1)+3\\
&=2m_{CA}(n-1)+2m_{AC}(n-2)+m_{CB}(n-2)+m_{BA}(n-2)+5\\
&=2m_{CA}(n-1)+2m_{AC}(n-2)+m_{CA}(n-1)+4\\
&=3m_{CA}(n-1)+2m_{AC}(n-2)+4\;.
\end{align*}$$
On the other hand, $m_{CA}(n)=m_{AC}(n+1)-2m_{AC}(n)-2$, so $$\begin{align*}
m_{CA}(n+1)&=m_{AC}(n+2)-2m_{AC}(n+1)-2\;,\\
m_{CA}(n-1)&=m_{AC}(n)-2m_{AC}(n-1)-2\;,
\end{align*}$$
and hence $$\begin{align*}
m_{AC}(n+2)-2m_{AC}(n+1)-2&=m_{CA}(n+1)\\
&=3m_{CA}(n-1)+2m_{AC}(n-2)+4\\
&=3m_{AC}(n)-6m_{AC}(n-1)+2m_{AC}(n-2)-2\;,
\end{align*}$$
or $$m_{AC}(n+2)=2m_{AC}(n+1)+3m_{AC}(n)-6m_{AC}(n-1)+2m_{AC}(n-2)\;.$$
Finally, shifting indices gives us $$m_{AC}(n)=2m_{AC}(n-1)+3m_{AC}(n-2)-6m_{AC}(n-3)+2m_{AC}(n-4)\;.$$
By direct computation the initial values are $m_{AC}(0)=0$, $m_{AC}(1)=2$, $m_{AC}(2)=7$, and $m_{AC}(3)=19$. The sequence continues $47, 113, 267, 629$ and is not in OEIS.
The auxiliary equation is $x^4-2x^3-3x^2+6x-2=0$, which reduces to $$(x-1)(x^3-x^2-4x+2)=0\;.$$ The cubic factor has three real roots; I didn’t feel like writing down the exact expressions for them, but this cubic equation calculator says that they are approximately $$\begin{align*}&2.34292308277717\;,\\
-&1.81360650264833\;,\text{ and}\\
&0.47068341987116\;.
\end{align*}$$
In the long run the first will dominate, and the sequence will grow by approximately that factor with each increase of one in the number of disks. For the record, $629/267\approx 2.3558$.
Each disk can go on one of three needles, so there are $3^n$ ways to assign disks to needles. Once you have a set of disks assigned to a needle, the order is determined. Now we have to worry about what of these are "the same" configuration. If the needles are labeled, we are done. If consider the needles interchangeable, most configurations have $3!=6$ alternatives, but the three configurations with all the disks on one needle are special, so we have $\frac {3^n-3}6+1=\frac {3^{n-1}+1}2$ configurations.
Best Answer
I will show it by induction on $n$ (the number of disks). Let $T(n)$ be the number of moves needed to go from an arbitrary configuration to another arbitrary configuration. Let $P(n)$ be the proposition "$T(n)\leq 2^n-1$". That is, $P(n)$ is the proposition "All starting and ending configurations of $n$ disks are at most $2^n-1$ moves apart.". I want to show that $P(n)$ is true for every natural number $n$.
For the base case, $P(0)$ is true, because it is clear that $T(0)=0\leq 2^0-1=0$.
For the inductive hypothesis, let's assume that $P(n-1)$ is true; that is, let's assume that it is true that $T(n-1)\leq 2^{n-1}-1$. Now, I will show that $P(n-1)$ implies $P(n)$.
First method
Suppose I have a configuration of $n-1$ disks. By the inductive hypothesis, we know that $T(n-1)\leq 2^{n-1}-1$. Now, let's consider what will change if we add one more disk (an $n^{th}$ disk), smaller than every other disk in the configuration, so that we have a situation where there are $n$ disks. Since this $n^{th}$ disk is the smallest one, it will always be on top in one of the three pegs, due to the rules of the problem.
The bottom $n-1$ disks will make $T(n-1)$ moves. For each move of the $n-1$ disks, in the worst case, the new smallest disk will be either on top of the disk that wants to move, or on top of the peg to which the disk wants to move. So, the new disk will have to make at most one move for each move of the other $n-1$ disks, that is, the new disk will make at most $T(n-1)$ moves. At last, when the $n-1$ disks are already at their correct positions in the end configuration, the new disk may have to make one more move to reach its correct position in the end configuration.
So, there will be at most $T(n) = T(n-1) + T(n-1) + 1 \leq 2^{n-1}-1+2^{n-1}-1+1 = 2^n - 2 + 1 = 2^n - 1$ moves. Therefore, $T(n) \leq 2^n - 1$, which shows that $P(n)$ is true.
Second method
I can also build the inductive step by considering that the new disk is the largest disk (instead of being the smallest one), as explained in the comments below.
Suppose we have a configuration of $n-1$ disks. By the inductive hypothesis, these $n-1$ disks need $T(n-1) \leq 2^{n-1}-1$ moves to reach any other configuration. Now, let's add an $n^{th}$ disk, which is the largest disk. We have two cases:
(1) If the largest disk doesn't move from the starting configuration to the end configuration, then we can just move the top $n-1$ disks as if there were only $n-1$ disks; so, in this case, it takes at most $2^{n-1} - 1$ moves. Therefore, it is true that $T(n) \leq 2^{n} - 1$. So, $P(n)$ is true in this case.
(2) If the largest disk moves, so we first have to move it to its end configuration. For this, we may have to move the top $n-1$ disks to a peg so that they are out of the way; by the inductive hypothesis, this takes at most $2^{n-1} - 1$ moves. Then, we move the largest disk to its correct position in the end configuration (1 more move). Then, we move the top $n-1$ disks to their correct positions in the end configuration (at most $2^{n - 1} - 1$ moves). The whole procedure takes at most $2^{n-1} - 1 + 1 + 2^{n-1} - 1 = 2^n - 1$ moves. So, $T(n) \leq 2^n - 1$. This shows that $P(n)$ is true in this case.