Please help me to find a combinatorial proof of the following identity:
(2n+2) C (n+1) = (2n) C (n+1)+2*(2n) C (n)+(2n) C (n-1)
Here ,n C r means n combination r ...............
Combi identity proof
- nahin munkar
- Posts:81
- Joined:Mon Aug 17, 2015 6:51 pm
- Location:banasree,dhaka
Re: Combi identity proof
Use symmetric identity that, $n C r = n C (n-r)$.
Then u get at R.H.S.: $(2n) C (n+1)=(2n) C (n-1)$; [1st & last term same.]
Then, use another summation identity:$nCr+nC(r+1)=(n+1)C(r+1)$.Then after some calculation u will get the form to prove: $(2n+2)C(n+1)=(2)*{{(2n+1)C(n+1)}}$.It's just easy simplification. Now, The rest is very easy.
Then u get at R.H.S.: $(2n) C (n+1)=(2n) C (n-1)$; [1st & last term same.]
Then, use another summation identity:$nCr+nC(r+1)=(n+1)C(r+1)$.Then after some calculation u will get the form to prove: $(2n+2)C(n+1)=(2)*{{(2n+1)C(n+1)}}$.It's just easy simplification. Now, The rest is very easy.
# Mathematicians stand on each other's shoulders. ~ Carl Friedrich Gauss
-
- Posts:12
- Joined:Sat Jan 23, 2016 7:55 pm
Re: Combi identity proof
#nahin munkar.......I have already solved it algebrically,by using some identity.But i need a combinatorial proof or explanation of it.
Re: Combi identity proof
Let's assume that there are $2n$ girls and $2$ boys.We want to make a team of $n+1$ members.We will count the number of such teams in two ways.There are $\displaystyle{\binom{2n+2}{n+1}}$ such teams.Now count it in another way.We may take $n-1$ girls and $2$ boys or $n$ girls and $1$ boy or $n+1$ girls and no boy in a team.So the total number of teams is $\displaystyle{\binom{2n}{n-1}\binom{2}{2}+\binom{2n}{n}\binom{2}{1}+\binom{2n}{n+1}\binom{2}{0}}$.
So,$\displaystyle{\binom{2n+2}{n+1}=\binom{2n}{n-1}\binom{2}{2}+\binom{2n}{n}\binom{2}{1}+\binom{2n}{n+1}\binom{2}{0}=\binom{2n}{n+1}+2\binom{2n}{n}+\binom{2n}{n-1}}$
So,$\displaystyle{\binom{2n+2}{n+1}=\binom{2n}{n-1}\binom{2}{2}+\binom{2n}{n}\binom{2}{1}+\binom{2n}{n+1}\binom{2}{0}=\binom{2n}{n+1}+2\binom{2n}{n}+\binom{2n}{n-1}}$
"Questions we can't answer are far better than answers we can't question"
-
- Posts:12
- Joined:Sat Jan 23, 2016 7:55 pm
Re: Combi identity proof
Thanks tanmoy for helping.............