Closed form solution to a recurrence relation (from a probability problem) Is there a closed form solution to the following recurrence relation?
$$P(i,j) =  \frac{i^{5}}{5i(5i-1)(5i-2)(5i-3)(5i-4)}\sum\limits_{k=0}^{j-5}(1-P(i-1,k))$$
where $P(i,j)=0$ for $j<5$.
The above recurrence is the solution I obtained to a probability problem, and I've been trying to simplify it even further by obtaining a closed formula.
The problem:

If we have $5i$ colored balls, $i$ of each color. Let's call the colors
  $1,2,3,4$ and $5$. We pick the balls without replacement until we obtain
  colors $1,2,3,4$ and $5$ in sequence.Then $P(i,j)$ is the probability that
  we will pick colors $1,2,3,4$ and $5$ in sequence in at most $j$ trials.

Note that, using a counting argument, one can show that
$$P(n,5n)= \frac{{n!}^{5}}{(5n)!}\sum\limits_{i=1}^n \frac{{(5n-4i)!}(-1)^{i+1}}{(n-i)!i!}$$

Odlyzko handles such problems in "Enumeration of Strings" (pages 205-228 in Combinatorial Algorithms on Words, Apostolico and Galil (eds), Springer, 1985). What you are looking for is strings over an alphabet of 5 symbols such that the string 12345 appears for the first time at the end. The autocorrelation polynomial of 12345 is just $c(z) = 1$. The generating function for the number of strings over an alphabet of $s$ symbols of length $n$ in which the pattern $p$ of length $k$ appears for the first time at the very end is:
$$
B_p(z) = \frac{c_p(z)}{(1 - s z) c_p(z) + z^k}
$$
The waiting time (the average length of strings in which the pattern appears for the first time at the very end) is just:
$$
W_p = B_p(1/s) = s^k c_p(1/s)
$$
In your particular case, $c_p(z) = 1$, so that $W_p = s^k = 5^5 = 3125$.
