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

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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

Answer 5

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

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