2
$\begingroup$

So the first thing I did was to multiply and then isolate the left-most term. That leaves me with $$ 2{2n \choose n} ={2n + 2\choose n + 1} - 2{2n \choose n -1} $$ No specific reasoning except that it looks cleaner, at least to me. Then the way I thought about it was that we are trying to make two $n$ member committees out of $n$ koalas and $n$ pandas. I was told when seeing subtraction I should think of complement but I don't really know how to incorporate the complement into this. Any way, am I on the right path or completely off. Thank you in advance for your time.

$\endgroup$
  • 1
    $\begingroup$ Don't know about your approach but have you tried using induction? $\endgroup$ – user265328 Sep 14 '15 at 5:26
2
$\begingroup$

HINT: Use the fact that $\binom{n}k=\binom{n}{n-k}$ to rewrite it as

$$\binom{2n+2}{n+1}=2\binom{2n}n+2\binom{2n}{n-1}=2\binom{2n}n+\binom{2n}{n-1}+\binom{2n}{n+1}$$

and use Pascal’s identity twice.

Note that $2\binom{2n}n$ doesn’t actually correspond to making two $n$-member committees from a group of $n$ koalas and $n$ pandas. If you’re going to try a combinatorial approach, your best bet is to write as I did above and consider making a committee of $n+1$ critters from a group of $n+1$ koalas and $n+1$ pandas. Suppose that there is exactly one black koala and exactly one black panda, all of the other critters being white. Then $2\binom{2n}n$ is the number of ways to choose $n$ of the white critters and one of the black ones. What do the other two terms on the righthand side of the expression represent?

$\endgroup$
1
$\begingroup$

Hint: Use the identity $$\binom{2n}{n}+\binom{2n}{n-1}=\binom{2n+1}{n}.$$ And the (algebraic) definition of binomial coefficient.

$\endgroup$
1
$\begingroup$

Note that $\binom {2n}{n-1}=\binom {2n}{n+1}$. So we can prove $$\binom {2n+2}{n+1}=\binom {2n}{n+1}+2\binom {2n}{n}+\binom {2n}{n-1}.$$ Now you can prove this by considering the number of ways to choose a committee of size $n+1$ from a group of $2n+2$. Suppose there are two people named A and B in the group. For the RHS, you need to count separately based on A and/or B being in the committee or not. This is a special case of Proving the combinatorial identity ${n \choose k} = {n-2\choose k-2} + 2{n-2\choose k-1} + {n-2\choose k}$.

$\endgroup$
1
$\begingroup$

Whenever you see these types of identities, at least I don't think like that. I think algebraically. Maybe long, but always correct.
We want to prove $$2{2n \choose n} ={2n + 2\choose n + 1} - 2{2n \choose n -1}$$ We know that $${2n\choose n}+{2n\choose n-1}={2n+1\choose n}$$ Multiplying by $2$ $$2{2n\choose n}+2{2n\choose n-1}=2{2n+1\choose n}$$ Now we have to prove that $$2{2n+1\choose n}={2n+2\choose n+1}$$ $$2.\frac{(2n+1)!}{(n+1)!n!}=\frac{(2n+2)!}{(n+1)!(n+1)!}$$ Let us assume the above, if it is true, we will get RHS=LHS, else, we will get a contradiction. So , by cancellation
$$2=\frac{2n+2}{n+1}$$ Which is true. Hence, $$2{2n\choose n}+2{2n\choose n-1}={2n+2\choose n+1}$$ So this expression is equivalent to your question.
As long as the proof of ${2n\choose n}+{2n\choose n-1}={2n+1\choose n}$ is concerned, I will prove the more general case- $${n\choose k}+{n\choose k-1}={n+1\choose k}$$ Proof: The given equation is same as $$\frac{n!}{k!(n-k)!}+\frac{n!}{(k-1)!(n-k+1)!}=\frac{(n+1)!}{k!(n-k+1)!}$$ Let us assume that with the same condition as before,
$$\frac{n!}{(k-1)!(n-k)!}(\frac1k+\frac1{n-k+1})=\frac{(n+1)!}{k!(n-k+1)!}$$ By cancelling and adding on the LHS, $$\frac{n+1}{k(n-k+1)}=\frac{n+1}{k(n-k+1)}$$ So LHS=RHS. Hence proved.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.