This is a cross-post with minor edits of the unanswered question https://math.stackexchange.com/questions/269904/pair-of-recurrence-relations.
I have a system of equations as follows.
$$M(p) = 1+\frac{n-p-1}{n}M(n-1) + \frac{2}{n} N(p-1) + \frac{p-1}{n}M(p-1)$$ $$N(p) = 1+\frac{n-p-1}{n}M(n-1) + \frac{p}{n}N(p-1)$$ $$M(1) = 1+\frac{n-2}{n}M(n-1) + \frac{2}{n}N(0)$$ $$N(0) = 1+\frac{n-1}{n}M(n-1)$$
$M(p)$ is defined for $1 \leq p \leq n-1$. $N(p)$ is defined for $0 \leq p \leq n-2$. Is it possible to work out what $M(n-1)$ is even approximately? I am interested in large $n$ solutions.
Examples. $n=2$ gives $M(1)=1+1+\frac{1}{2}M(1) \implies M(1) = 4$. $n=3$ gives four equations in four unknowns and $M(2) = \frac{33}{5}$.
There is a graph of the solutions for $M(n-1)$ for $n\leq 10000$ in the math.stackexchange version of the question (new users can't post images here). Using least squares fitting, the curve is roughly $0.7n^{1.49}+301$. The crosses represent the fitted points which we can see are very close to the line.
In fact by solving instances as large as $n =1000000$ it appears the value of $M(n-1)$ is $\Theta(n^{3/2})$. Does anyone have any idea how to attempt to prove this?
