Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This is a cross-post with minor edits of the unanswered question http://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?

share|improve this question
    
Why the "differential equations" tag? –  Gerry Myerson Jan 17 '13 at 22:05
    
That was a typo. Thanks. –  majid Jan 18 '13 at 6:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.