Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How to solve the following 2-dimensional recurrence relation?

Let $n, n'$ be natural numbers $> 0.$ Let $r$ be a positive integer $\ge 0.$ $$ P(n+n',r) = \sum_{i=0}^{r} P(n, i)*P(n', r-i) $$ where the base case is $$ P(1, r) = 1, \quad P(n, 0)=1$$

$P(n,r)$ is only defined for $n\ge1$ and $r\ge0$

share|improve this question
First, the recursion in your post is not well defined (what are $n'$ and $r'$?). Second, an approach to this kind of recursion is to consider doubly-indexed generating series. That is, one uses $\sum\limits_n\sum\limits_rP(n,r)x^ny^r$ instead of $\sum\limits_nP(n)x^n$. –  Did Mar 26 '12 at 7:38
I typed in the question wrong. I have corrected it now. –  Euclidean Mar 27 '12 at 3:26
I've made a major edit to the body of the post. I've included the original post for reference. Please make sure that I did not tamper the semantics. –  user2468 Mar 27 '12 at 3:44
Thanks, it is perfectly fine. –  Euclidean Mar 27 '12 at 3:53
@user1278543 I see you are new to math.SE. Welcome aboard! The best way to get help around here is to state the problem clearly (in a separate paragraph), and define all the variables, and their range of values. Also, it is usually better to tell what did you try as well, and in which step you did fail. Learning some LaTeX can help, but oh well. It takes time. –  user2468 Mar 27 '12 at 4:12
show 2 more comments

2 Answers

up vote 3 down vote accepted

Let me assume that your problem is really the following one:

Find every family of numbers $(P(n,r))_{n\geqslant1,r\geqslant0}$ such that, for every $n\geqslant1$, $m\geqslant1$ and $r\geqslant0$, $P(n,0)=P(1,r)=1$ and $$ P(n+m,r)=\sum_{s=0}^rP(n,s)P(m,r-s). $$

A method to solve this is to introduce, for each $n\geqslant1$, the formal series $Q_n(x)$ defined by $$ Q_n(x)=\sum_{r=0}^{+\infty}P(n,r)x^r, $$ for some parameter $x$, and to use these objects as follows:

  1. Identify $Q_1(x)$.
  2. Translate the recursion above into a relation between every $Q_{n+m}(x)$, $Q_n(x)$ and $Q_m(x)$.
  3. Deduce from 1. and 2. an explicit formula for every $Q_n(x)$.
  4. Deduce from 3. the value of every $P(n,r)$.

Now, shoot...

Edit: For different initial conditions such as $P(n,0)=1$ and $P(1,r)=\cos(r)$, the method stays exactly as described above, only the result of step 1. changes and the feasability of step 4. is lessened. In this specific case, one gets $$ \sum\limits_{r=0}^{+\infty}P(n,r)x^r=\left(\frac{1-x\cos 1}{1-2x\cos 1+x^2}\right)^n. $$ To see this, note that $P(1,r)$ is the real part of $\mathrm e^{\mathrm i r}$, hence $Q_1(x)$ is the real part of $$ \sum\limits_{r=0}^{+\infty}\mathrm e^{\mathrm i r}x^r=\frac1{1-x\mathrm e^{\mathrm i}}=\frac{1-x\mathrm e^{-\mathrm i}}{|1-x\mathrm e^{\mathrm i}|^2}=\frac{1-x\cos1+\mathrm ix\sin1}{1-2x\cos 1+x^2}. $$

share|improve this answer
In a comment now deleted, you explained that your method was to choose (what I denote) $Q_1(x)$ (equal to some series you liked) and then to proceed. This cannot do, one is not free to choose $Q_1$... –  Did Mar 27 '12 at 5:33
Please signal if any step from 1. to 4. causes you problems. –  Did Mar 27 '12 at 5:34
You now reproduced and amplified said comment into an answer. It appears that what you really do is to guess the series $Q_1$ and to check that $Q_n=(Q_1)^n$ for every $n$, solves the recursion. –  Did Mar 27 '12 at 5:49
I think you have made some mistake in the derivation of P(n,r). For example take n=1, then your $Q_1(x)$ depends upon r. Please correct it. –  Euclidean Mar 27 '12 at 15:00
Done, $\cos r$ was in fact $\cos 1$. –  Did Mar 27 '12 at 15:57
show 1 more comment

This is how i solved it -

Let $P(n,r)$ denote the coefficient of ${ x }^{ r }$ in

$$\left( 1+x+{ x }^{ 2 }.....\infty \right) *\left( 1+x+{ x }^{ 2 }.....\infty \right) *\left( 1+x+{ x }^{ 2 }.....\infty \right) ......n\quad terms$$ I chose this polynomial so that the base case is satisfied. Now let's divide n terms each of which equals 1/(1-x) into two parts of size $n_1$ and $n_2$ i.e. $(n_1+n_2=n)$. If we find coefficient of $x^i (i<=r)$ in the $n_1$ terms i.e $P(n_1, i)$ then we have to multiply it with coefficient of $x^{r-i}$ in the $n_2$ terms i.e. $P(n_2, r-i)$ where i ranges from 0 to r. Hence the recursive relation holds. We know that coefficient of ${ x }^{ r }$ in ${ (1-x) }^{ -n }$ is $^{n-1+r}$ $C_{n-1}$ .

Hence $$P(n,r)\quad= \quad^{n-1+r}\hspace{5 px}C_{n-1}$$

But what if base case is changed to something like this

$$P(n,0)=1 \quad and \quad P(1, r)=cos(r)$$

share|improve this answer
add comment

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.