Bound on a two-dimensional recursive series

Question

For $n,k\in\mathbb{N}$, let $f(n,k)$ be defined as follows.

If $n \geq k$ and $n > 2$, then $$ f(n,k) = \frac{k(n-k)}{n(n-1)}f(n-2,k-1) + \frac{k(k-1)}{n(n-1)}f(n-2,k-2) + \frac{n-k}{n}f(n-1,k) + \frac{k}{n}, $$ if $n < k$, then $$ f(n,k) = 0, $$ otherwise $$ f(n,k) = \min\{1,k\}. $$

I have been trying to prove that $$ \frac{f(n,\lceil n/2\rceil)}{\lceil n/2\rceil}\geq\frac{2}{3} $$ holds for all $n\in\mathbb{N}$ without any success. The statement is computer-verified for $n,k\leq 1000$. Possibly all I am missing is the correct inductive hypothesis.

Answer 1

This is not (yet) a solution, but a step towards it.

Consider a generating function $$F(x,y) := \sum_{n=0}^\infty \sum_{k=0}^n f(n+1,k+1) x^n y^k.$$ The recurrence for $f(n,k)$ implies the following PDE: \begin{split} & x \,y^{3} \left(y-1 \right) \frac{\partial^{2}}{\partial y^{2}}F \! \left(x , y\right) +x \left(x-1 \right) \frac{\partial^{2}}{\partial x^{2}}F \! \left(x , y\right) +\left(x y -1\right) x y \frac{\partial^{2}}{\partial x \partial y}F \! \left(x , y\right) \\ + &\left(6xy^{2}-2xy - 1\right) y \frac{\partial}{\partial y}F \! \left(x , y\right) + \left(2x^{2} y +3 x -2\right) \frac{\partial}{\partial x}F \! \left(x , y\right) \\ + & \left(6xy^{2}+2xy+1\right) F \! \left(x , y\right)+\frac{3 x y -2 y -1}{(x-1)^2(xy-1)^3} = 0 \end{split} with the boundary conditions $F(0,y)=1$ and $F(x,0)=\frac1{1-x}$.

I did not try to solve it manually, but Maple does solve it (more specifically, it solves the aforementioned PDE times $(x-1)^2(xy-1)^3$) in general, but cannot take into account the boundary conditions. This gives a hope that the PDE is soluble for the given boundary conditions as well.

Having an explicit formula for $F(x,y)$ will likely provide one for $f(n,\lceil n/2\rceil)$, which then can greatly help in establishing the inequality in question.