0
$\begingroup$

Let $p\in \mathbb{R}$ and $n\in \mathbb{N}$ and $$\binom{p}{n}=\frac{p(p-1)(p-2)...(p-n+1)}{n!}$$

b) Prove $$n\binom{p}{n}=p\binom{p-1}{n-1}$$

Thanks for all the help with a! I definitely understand it now. Now part b is simply asking me to multiply those, correct? I did that and it just seems to easy. Also I never used the fact that $$\binom{p}{0}=1.$$ Was I supposed to use it for b?

$\endgroup$
9
  • $\begingroup$ jut put it into your formula for $\binom{p}{n}$ and calculate. There is also the possibility to prove these identities with combinatorial arguments without making calculations. $\endgroup$
    – M.U.
    Sep 16, 2015 at 17:50
  • $\begingroup$ in both cases the lhs and the rhs of the equations are real numbers. You are supposed to show they are equal. How you do this is up to you. $\endgroup$
    – Thomas
    Sep 16, 2015 at 17:51
  • $\begingroup$ You're on the right track, and a common denominator is a good idea. It might also help to write out what you're aiming for ($p \choose n$) somewhere, so you know what simplifying to do. $\endgroup$ Sep 16, 2015 at 17:56
  • 2
    $\begingroup$ This question is the same as:math.stackexchange.com/questions/20475/… $\endgroup$
    – NoChance
    Sep 16, 2015 at 18:28
  • 1
    $\begingroup$ @AustinMohr how can I find out if my question is a duplicate or not? I was searching and could not find it, but maybe I'm looking in the wrong place? I"m a fairly new infrequent user of Stack Exchange, so please forgive me. $\endgroup$
    – Kristin
    Sep 16, 2015 at 19:24

5 Answers 5

1
$\begingroup$

$$\binom{p-1}{n-1}=\frac{(p-1)(p-2)(p-3)...(p-n+1)}{(n-1)!}=\frac{n(p-1)(p-2)(p-3)...(p-n+1)}{n!} $$

so using the common denominator we can now add the fractions $$\binom{p-1}{n}+\binom{p-1}{n-1} $$ $$= \frac{n(p-1)(p-2)(p-3)...(p-n+1)+(p-1)(p-2)(p-3)...(p-n+1)(p-n)}{n!} $$ $$= \frac{(p-1)(p-2)(p-3)...(p-n+1)}{n!}(n+p-n)=\binom pn $$

$\endgroup$
1
$\begingroup$

Even though $p \in {\mathbb R}$, there is a combinatorial way around that to show these identities hold. Namely, if you show that two polynomial expressions are equal for infinitely many positive integer values $p$, then the two polynomials are equal for ALL real values $p$, because a difference of two different polynomials can only have a finite number of zeros. So just forget about the fact that $p$ is real, and then you can use combinatorics (arguing in terms of choosing subsets) to prove your formulas are true for positive integers $p$, and then you are done.

$\endgroup$
0
$\begingroup$

To prove two algebraic expressions are equal, you typically write out each one and try to simplify it, and see whether the simplified versions of the expression are equal. For instance, to prove that $$ x^2 - 1 = (x + 1) (x -1) $$ you look at the left side and say "That looks simple already." Then look at the right and say $$ (x+1)(x-1) = x(x-1) + 1(x-1) = x^2 - x + x - 1 = x^2 - 1. $$ Hunh! Look at that...it's equal to the thing I had on the left, so I'm done!"

In your case, try pluggin the definition into the two expressions on the left in (a), and the one expression on the right, and see whether the resulting things can be simplified into one another.

$\endgroup$
0
$\begingroup$

These can be done more elegantly using product notation ...

$$p \binom {p-1}{n-1} = n(\frac pn ) \prod_{i=1}^{n-1}\frac{p-n+i}{i}$$

$$= n \prod_{i=1}^{n}\frac{p-n+i}{i}= n \binom pn$$

$\endgroup$
0
$\begingroup$

I guess an intuitive way to prove (a) is as follows. Consider an $n\times (p-n)$ grid. Suppose you want to move from the lower left corner $A$ of this grid to the higher right corner $B$, and that you are only allowed to move right (r) or up (u). Therefore, each path from $A$ to $B$ will be a sequence similar to "u,r,u,u,r....", etc. Thus, you have $\frac{p!}{n!(p-n)!}$ ways to go from $A$ to $B$. Now, consider the following example (in which $n=3$ and $p=6$) :

enter image description here

Let's note $N(X,Y)$ the number of paths we have between two points $X$ and $Y$ (still only using r or u movements). From the figure, we see that

$N(A,B)=N(A,C)+N(A,D)=\frac{(p-1)!}{n!(p-1-n)!}+\frac{(p-1)!}{(n-1)!(p-n)!}$

Which is what was asked in (a).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .