Combi identity proof

For discussing Olympiad Level Combinatorics problems
Md Ashraful Kader
Posts:12
Joined:Sat Jan 23, 2016 7:55 pm
Combi identity proof

Unread post by Md Ashraful Kader » Fri May 27, 2016 10:48 pm

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

User avatar
nahin munkar
Posts:81
Joined:Mon Aug 17, 2015 6:51 pm
Location:banasree,dhaka

Re: Combi identity proof

Unread post by nahin munkar » Sat May 28, 2016 1:12 am

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. :D
# Mathematicians stand on each other's shoulders. ~ Carl Friedrich Gauss

Md Ashraful Kader
Posts:12
Joined:Sat Jan 23, 2016 7:55 pm

Re: Combi identity proof

Unread post by Md Ashraful Kader » Sat May 28, 2016 2:11 am

#nahin munkar.......I have already solved it algebrically,by using some identity.But i need a combinatorial proof or explanation of it.

tanmoy
Posts:312
Joined:Fri Oct 18, 2013 11:56 pm
Location:Rangpur,Bangladesh

Re: Combi identity proof

Unread post by tanmoy » Sat May 28, 2016 6:43 pm

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}}$
"Questions we can't answer are far better than answers we can't question"

Md Ashraful Kader
Posts:12
Joined:Sat Jan 23, 2016 7:55 pm

Re: Combi identity proof

Unread post by Md Ashraful Kader » Sat May 28, 2016 11:46 pm

Thanks tanmoy for helping............. :D

Post Reply