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
    This is probably an English translation issue, but what does it mean to "solve the recurrence" if it does not mean that you are "able to prove that $N(r,p) = \binom{p+r-3} {p-3}$."2012-12-19
  • 0
    It seems you have already solved the recurrence, and then proved it. $N(r,p) = N(r,p-1) + N(r-1,p)$ suggests something like Pascal's triangle rotated by 45 degrees while the starting conditions suggest a shift by 3.2012-12-19
  • 0
    I want to solve this recurrence . What is the procedure ?2012-12-19
  • 0
    What we don't understand is the difference between proving $N(r,p)=(p+r-3){\rm-choose-}(p-3)$, which you write that you are able to do, and solving the recurrence.2012-12-20
  • 0
    Plz check the edited version of my Question . Hope the confusion will not arise any more. @Thomas Andrews2012-12-21
  • 0
    N(r,p)=((p+r−3),(p−3)) . That means N(r,p) is the number of ways to choose (p-3) things from (p+r-3) .2012-12-21
  • 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.