4
$\begingroup$

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$

  • 0
    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$.2012-03-26
  • 0
    I typed in the question wrong. I have corrected it now.2012-03-27
  • 0
    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.2012-03-27
  • 0
    Thanks, it is perfectly fine.2012-03-27
  • 0
    @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.2012-03-27
  • 0
    If $r \in \mathbb{Z^+}$, it is superfluous to say $r \geq 0$, since it is implied that $r > 0$. The same goes for $n$ and $n'$, since $\mathbb{N} = \mathbb{Z^+}$ (by most definitions anyway). Did you mean something slightly different?2012-03-27
  • 0
    I may be wrong on this, but I think the base case may be contradictory. Since if $P(1, r) = 1$ and $P(n, r < 0) = 0$, what is the value of, for example, $P(1, -1)$?2012-03-27

2 Answers 2

3

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}. $$

  • 0
    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$...2012-03-27
  • 0
    Please signal if any step from 1. to 4. causes you problems.2012-03-27
  • 0
    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.2012-03-27
  • 0
    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.2012-03-27
  • 0
    Done, $\cos r$ was in fact $\cos 1$.2012-03-27
  • 0
    So you are saying that $Q_{n+m}$ = $Q_n*Q_m$. But how do you find the value of $Q_1$ (For the second base case i.e. P(1, r)=cos(r))?2012-03-27
3

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)$$