1
$\begingroup$

I have the following recurrence which I can not solve .

Trivial Case : 1. N(o,p) = 1 for p>=3 2. N(r,3) = 1 for r>=0 Recurrence : 1. N(r,p) = N(r,p-1) + N(r-1,p) 

What is the value of N(r,p) ? I want to solve the recurrence and want to find the value of N(r,p) . Plz help me to find the value of this recurrence .

  • 0
    In the question, you ask for the value of $N(r,p)$. In the comment, you **give** the value of $N(r,p)$. You have only succeeded in compounding the confusion.2012-12-22

1 Answers 1

2

I think the comments really say what need to be said. Nevertheless, I'd like to try to expound on this.

The question was to "find the value" of $N(r,p)$, but it has been granted that $N(r,p) = \binom{p+r-3}{p-3}$. If the question is whether a better "solution" (or "value"?) exists, I would have to say no. I would point you to a definition of Binomial Coefficients in case you are unfamiliar with the method of calculating these numbers.

Perhaps the result $\binom{p+r-3}{p-3}$ does not satisfy because it does not resemble expressions such as $p+r$ or $\frac{p^2}{\sqrt{r}}$. The fact is, we cannot express the binomial coefficients (in general) in terms of $+$, $-$, $\times$, $\div$, $\sqrt{}$, and/or exponents, unless we are willing to throw in some extra dots (ellipsis) to indicate a certain pattern:

$ \binom{n}{m} = \frac{n(n-1)(n-2) \cdots (n-m+1)}{m(m-1)(m-2)\cdots 1} $

Incidentally, your recurrence $N(r,p)$ could be expressed in this way by:

$ N(r,p) = \frac{(p+r-3)(p+r-4)\cdots (r+1)}{(p-3)(p-4) \cdots 1} $

To summarize, the best solution to your recurrence is $N(r,p) = \binom{p+r-3}{p-3}$. It is what it is.