prove the combinatorial identity: $ {2n \choose n} + {2n\choose n-1} = (1/2){2n + 2 \choose n + 1}$

Question

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.

Answer 1

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

Answer 2

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?

Answer 3

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

Answer 4

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.