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