I have a recurrence that looks like
$$p(i,j,k) = \frac{j}{n}p(i-1,j-1,k-1) + \frac{i-j}{n}p(i-1,j,k-1)$$
$$p(i,0,k) = 1$$ $$p(i,j,0) = 0$$ $$p(0,j,k) = 0$$
The base cases are to be considered in order from top to bottom. So the first matching one applies.
We define the function only when $0\leq i,k \leq n$ and $0\leq j \leq 2$.
I would like to prove that $$p\left(n,2,\left\lceil \sqrt{n} \right\rceil\right) \geq \frac{1}{2n}$$
for $n\geq 2$.
The recurrence measures the probability of events occurring in a Markov chain. I have computed the values for all $n<300$ and it does hold for those.
Is there a direct way of proving this without having to solve the recurrence fully? It looks like you should be able to prove it by induction but I can't exactly see how.
Update. As suggested in the comments, we can solve $p(i,1,k)$ explicitly just by unrolling as the recurrence is simply $$p(i,1,k) = \frac{1}{n} + \frac{i-1}{n} p(i-1,1,k-1)$$
and we can also assume $k \leq i$ so we know exactly how many steps to unroll for. However, I am not sure how much this helps.
I write an exact solution of the equation and hope that it helps to you to obtain some estimate.
I suppose that $i>k$.
1) Let $j=1$. Setting $p(i,1,k)=\frac{(i-1)!}{n^k}r(i,k)$ we have $$ r(i,k)=\frac{n^{k-1}}{(i-1)!}+r(i-1,k-1). $$ From here $$ r(i,k)=\frac{1}{n^{i-k}}\sum_{\alpha=i-k}^{i-1}\frac{n^\alpha}{\alpha!}\approx \frac{1}{n^{i-k}}(e^{i-1}-e^{i-k}). $$
2) Let $j=2$. Setting $p(i,2,k)=\frac{(i-2)!}{n^k}t(i,k)$ we have $$ t(i,k)=2r(i,k)+t(i-1,k-1). $$ From here $$ t(i,k)=2(r(i,k)+r(i-1,k-1)+\ldots +r(i-k+2,2))\approx \ldots $$ (here you have a geometric progression). Of course, ``$\approx$'' should be used cautiously.