The setup:
We have an unlimited supply of balls and $k$ boxes. In every step, we randomly (all of them have the same probability) choose a box and put a ball in it. Let $X_n$ be the number of nonempty boxes after $n$ steps.
Question:
Find the transition matrix after $n$ steps. (That is a matrix composed of probabilities $p_{ij}^{(n)}$ that the process will go from state $i$ to state $j$ in $n$ steps)
This question is from an exam question that our lecturer decided to cross out from the test due to its difficulty with respect to the time limit. Since I already attempted to work it out before the decision and he didn't really check my working on it, I ask Math.SE to help me here.
Starting out from $n=1$, we have $$P= \left( \begin{array}{ccccccc} 0 & 1 &0&0&0&\cdots&0\\ 0 & \frac 1k & \frac{k-1}k &0 &0& \cdots&0\\ 0 &0& \frac 2k & \frac{k-2}k &0& \cdots&0\\ \vdots & \vdots & \vdots & \vdots & \ddots &\vdots & \vdots & \\ 0 &0 &0&0&0&\cdots&1\\ \end{array} \right)$$ Where the entry $(i,j)$ represents the probability $p_{ij}$, that is the probability that after one step, the process will go from state $i$ to state $j$
Now, for the process to go from state $i$ to state $j$, it definifely has to go forth $j-i$ times, the probability of which is $$ \Big(\frac {k-i}k \Big)\Big(\frac {k-i-1}k \Big)\cdots \Big(\frac {k-j+1}k \Big)$$ In the remaining time, the process has to wait. It can wait in any state $i$ with probability $\frac ik$ and it has to wait $n-(j-i)$ times. Thus the probability of waiting like that is $$ \Big(\frac ik \Big)^{x_1}\Big(\frac {i+1}k \Big)^{x_2}\cdots\Big(\frac jk \Big)^{x_p} $$ Where $p=j-i+1$ and $$x_1+x_2+\cdots+x_p=n-(j-i)\tag{1}$$
Putting this all together, we have (for $j\geq i$) $$ p_{ij}^{(n)} = \sum\limits_{\{x_1,\dots,x_p\}} \Big(\frac ik \Big)^{x_1}\Big(\frac {k-i}k \Big)\Big(\frac {i+1}k \Big)^{x_2}\Big(\frac {k-i-1}k \Big)\cdots\Big(\frac {k-j+1}k \Big)\Big(\frac jk \Big)^{x_p} $$ Where $\{x_1,\dots,x_p\}$ satisfy the equality $(1)$
Is this correct? Hope this is not going to be too tedious for anyone to go through, I was waiting all week to find out whether I am correct or not and was somehwat disappointed finding out my work has barely been read. Thank you!
Here is an interpretation of the original question. Assume the states are $S_i$, each representing the event that there are exactly $i$ non-empty boxes. Clearly, we have $$p_{ij} = \begin{cases}i/k & \text{if }i = j \\ 1-i/k & \text{if } j = i + 1 \\ 0 & \text{otherwise}.\end{cases},$$ where $i,j\in\{0,1,\dots, k\}$. This gives us a Markov chain with transition matrix $P = (p_{ij})$, which matches the matrix in your proof. What follows in your proof is absolutely correct.
However, one can also use standard tools in matrix theory to compute $P^n$. Note that $0/k, 1/k, \dots, k/k$ are the eigenvalues of $P$. For an eigenvalue of the form $\lambda_i = i/k$, the corresponding eigenvector is $v_i$ with $$v_{ij} = \begin{cases}(-1)^{k-j}{k-i\choose k-j}& \text{if }j \ge i, \\ 0 & \text{otherwise},\end{cases}$$ so that $v_iP = \lambda_iv_i$. (One has to check this is true though.) Set $$V = \begin{pmatrix}v_0 \\ \vdots \\ v_k\end{pmatrix}.$$ We thus have $VP = DV$, where $D = \operatorname{diag}(\lambda_0, \dots, \lambda_n)$. Hence we know $P^n = V^{-1}D^nV$. For example, when $k = 5$, $$V = \begin{pmatrix}0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & -1 & 1 \\ 0 & 0 & 0 & 1 & -2 & 1 \\ 0 & 0 & -1 & 3 & -3 & 1 \\ 0 & 1 & -4 & 6 & -4 & 1 \\ -1 & 5 & -10 & 10 & -5 & 1\end{pmatrix}\text{ and }D = \begin{pmatrix}0/5 & & & & & \\ & 1/5 \\ & & 2/5 \\ & & & 3/5 \\ & & & & 4/5 \\ & & & & & 5/5\end{pmatrix}.$$