Finding again the stationary distribution of a markov chain I am asked to compute the stationary distribution of the markov chain with state space $E=\{0\dots,n\}$ and transition matrix below:
\begin{bmatrix} 
 0       & 1             \\
 \frac{1}{n}     &  0 & \frac{n-1}{n} \\
      & \frac{2}{n}     &  0 &   \frac{n-2}{n}   &          \\
      &      &  \ddots &   \ddots   & \ddots    \\
    &      &   &   \frac{n-1}{n}   & 0 & \frac{1}{n}   \\
     &     &   &     & 1 &   0   &  \\
\end{bmatrix}
I used $\pi P =\pi$ and I got:
$\pi_0=\frac{1}{n}\pi_1 \\\pi_1 = \pi_0+\frac{2}{n}\pi_2 \\ \pi_2 =\frac{n-1}{n}\pi_1 +\frac{3}{n}\pi_3 \\ \pi_3 =\frac{n-2}{n}\pi_2 +\frac{4}{n}\pi_4\\ \pi_4 =\frac{n-3}{n}\pi_3 +\frac{5}{n}\pi_5\\ $
Working from there I got:
$\pi_0 = \frac{1}{n}\pi_1 \\\pi_1 =n.\pi_0 \\ \pi_2=\frac{n^2-n}{2} \pi_0 \\ \pi_3 = \frac{n^3-3n^2+2n}{6} \pi_0 \\ \pi_4 = \frac{n^4-6n^3+11n^2-6n}{24} \pi_0 \\ \sum_{k=0}^\infty \pi_k = 1$
I tried fiddling with it and spotting a pattern for $\pi_k$ but I cant see to find $\pi_k$ for all $k\in E=\{0,\dots,n\}$. How would I finish this problem?
This is a follow-up from my previous question Calculating stationary distribution of markov chain , Sasha kindly showed me a way to find the stationary distribution, and I understood that method, but I don't think i've come across that method before in my lecture. I was wondering if it was possible to compute the stationary distribution using the method I did above, but I can't seem to get to the end..
 A: Thus, $\pi_1=n\pi_0$ and $\pi_2=\frac12n(n-1)\pi_0$, as you wrote, but $\pi_3$ is not what you wrote since $\pi_3=\frac16(n^3-3n^2+2n)\pi_0$. Can you see a pattern? 
Hint: Find the factorization of $n^3-3n^2+2n$.
Follow-up: Since you found $\pi_3=\frac16n(n-1)(n-2)\pi_0$, factorials begin to enter the picture. So let us turn $\pi_3$ into an expression with factorials. Clearly, $n(n-1)(n-2)=\frac{n!}{(n-3)!}$ and $6=3!$ hence $\pi_3=\frac{n!}{3!(n-3)!}\pi_0$. You might also recognize this as $\pi_3={n\choose 3}\pi_0$. I am pretty sure you can take up things from here.
A: Write your solutions for the $\pi_k$ a little differently:
$$\begin{align*}
\pi_1&=n\pi_0\\
\pi_2&=\frac12n(\pi_1-\pi_0)=\frac12n(n-1)\pi_0\\
\pi_3&=\frac13n\left(\pi_2-\frac{n-1}n\pi_1\right)=\frac13n\left(\frac12n(n-1)-(n-1)\right)\pi_0\\
&=\frac13n(n-1)\left(\frac12n-1\right)=\frac16n(n-1)(n-2)\\
\pi_4&=\frac14n\left(\pi_3-\frac{n-2}n\pi_2\right)\\
&=\frac14n\left(\frac16n(n-1)(n-2)-\frac{n-2}n\cdot\frac12n(n-1)\right)\pi_0\\
&=\frac14n\left(\frac16n(n-1)(n-2)-\frac12n(n-1)(n-2)\right)\pi_0\\
&=\frac1{24}n(n-1)(n-2)(n-3)\pi_0\;.
\end{align*}$$
At this point the pattern should be pretty obvious, and the natural way to prove it is by induction.
