Putnam, 1962: Summing Binomials

For discussing Olympiad Level Combinatorics problems
User avatar
sowmitra
Posts:155
Joined:Tue Mar 20, 2012 12:55 am
Location:Mirpur, Dhaka, Bangladesh
Putnam, 1962: Summing Binomials

Unread post by sowmitra » Tue Sep 04, 2012 9:31 pm

Given, $n \in \mathbb{N}$, show that,
\[\displaystyle\sum^{n}_{r=1}r^{2}\binom{n}{r}=n(n+1)2^{n-2}\]
Last edited by sowmitra on Tue Sep 04, 2012 9:37 pm, edited 1 time in total.
"Rhythm is mathematics of the sub-conscious."
Some-Angle Related Problems;

User avatar
sowmitra
Posts:155
Joined:Tue Mar 20, 2012 12:55 am
Location:Mirpur, Dhaka, Bangladesh

Re: Putnam, 1962: Summing Binomials

Unread post by sowmitra » Tue Sep 04, 2012 9:36 pm

Lemma:
Prove that,
$\displaystyle\sum^{n}_{r=1}r\binom{n}{r}=1\binom{n}{1}+2\binom{n}{2}+3\binom{n}{3}+...+n\binom{n}{n}=n.2^{n-1}$
"Rhythm is mathematics of the sub-conscious."
Some-Angle Related Problems;

User avatar
SANZEED
Posts:550
Joined:Wed Dec 28, 2011 6:45 pm
Location:Mymensingh, Bangladesh

Re: Putnam, 1962: Summing Binomials

Unread post by SANZEED » Thu Sep 06, 2012 5:57 am

$\displaystyle\sum_{r=1}^{n}r^{2}\binom{n}{r}=\displaystyle\sum_{r=1}^{n}nr\binom{n-1}{r-1}$ [Since $\binom{n}{r}=\frac{n}{r}\binom{n-1}{r-1}$]$=n\displaystyle\sum_{r=1}^{n}r\binom{n-1}{r-1}=n\displaystyle\sum_{r=1}^{n}(r-1)\binom{n-1}{r-1}+n\displaystyle\sum_{r=1}^{n}\binom{n-1}{r-1}$
Which is equal to $n\displaystyle\sum_{i=0}^{n-1}i\binom{n}{i}+\displaystyle\sum_{i=0}^{n-1}\binom{n-1}{i}=n\times (n-1)\times 2^{n-2}+2^{n-1}$ and the desired result follows.
Last edited by SANZEED on Fri Sep 07, 2012 11:15 pm, edited 1 time in total.
$\color{blue}{\textit{To}} \color{red}{\textit{ problems }} \color{blue}{\textit{I am encountering with-}} \color{green}{\textit{AVADA KEDAVRA!}}$

User avatar
sowmitra
Posts:155
Joined:Tue Mar 20, 2012 12:55 am
Location:Mirpur, Dhaka, Bangladesh

Re: Putnam, 1962: Summing Binomials

Unread post by sowmitra » Fri Sep 07, 2012 6:20 pm

SANZEED wrote:$\displaystyle\sum_{r=1}^{n}r^{2}\binom{n}{r}=\displaystyle\sum_{r=1}^{n}nr\binom{n-1}{r-1}$ [Since $\frac{n}{r}\binom{n}{r}=\binom{n-1}{r-1}$]
I think, it is, $\displaystyle\binom{n}{r}=\frac{n}{r}\binom{n-1}{r-1}$ ;)
"Rhythm is mathematics of the sub-conscious."
Some-Angle Related Problems;

User avatar
SANZEED
Posts:550
Joined:Wed Dec 28, 2011 6:45 pm
Location:Mymensingh, Bangladesh

Re: Putnam, 1962: Summing Binomials

Unread post by SANZEED » Fri Sep 07, 2012 11:16 pm

:oops: Sorry, I have edited the typo.
$\color{blue}{\textit{To}} \color{red}{\textit{ problems }} \color{blue}{\textit{I am encountering with-}} \color{green}{\textit{AVADA KEDAVRA!}}$

User avatar
sm.joty
Posts:327
Joined:Thu Aug 18, 2011 12:42 am
Location:Dhaka

Re: Putnam, 1962: Summing Binomials

Unread post by sm.joty » Tue Sep 18, 2012 3:24 pm

using second derivative can give a nice proof. :)
হার জিত চিরদিন থাকবেই
তবুও এগিয়ে যেতে হবে.........
বাধা-বিঘ্ন না পেরিয়ে
বড় হয়েছে কে কবে.........

User avatar
SANZEED
Posts:550
Joined:Wed Dec 28, 2011 6:45 pm
Location:Mymensingh, Bangladesh

Re: Putnam, 1962: Summing Binomials

Unread post by SANZEED » Tue Sep 18, 2012 11:00 pm

sm.joty wrote:using second derivative can give a nice proof. :)
And here is the proof:
From the binomial theorem,we have,$(x+y)^{n}=\displaystyle\sum_{r=0}^{n}\binom{n}{r}x^{n-r}y^{r}$. Substitute $x=1$, then $(1+y)^{n}=\displaystyle\sum_{r=0}^{n}\binom{n}{r}y^{r}$. Now taking the second derivative on each side, we have that $n(n-1)(1+y)^{n-2}=\displaystyle\sum_{r=0}^{n}r(r-1)\binom{n}{r}y^{r-2}\Rightarrow n(n-1)(1+y)^{n-2}=\displaystyle\sum_{r=0}^{n}r^{2}\binom{n}{r}y^{r-2}-\displaystyle\sum_{r=0}^{n}r\binom{n}{r}y^{r-2}$. Substitute $y=1$ and use the lemma $\displaystyle\sum_{r=0}^{n}r\binom{n}{r}=n\cdot 2^{n-1}$ (Which can also be proved taking first derivative instead of second). The result then follows.
$\color{blue}{\textit{To}} \color{red}{\textit{ problems }} \color{blue}{\textit{I am encountering with-}} \color{green}{\textit{AVADA KEDAVRA!}}$

User avatar
Tahmid Hasan
Posts:665
Joined:Thu Dec 09, 2010 5:34 pm
Location:Khulna,Bangladesh.

Re: Putnam, 1962: Summing Binomials

Unread post by Tahmid Hasan » Tue Oct 30, 2012 2:29 pm

Masum wrote: The Instructor and the captain same- we have $2^{n-2}*n^2$ (why?). And if not, $2^{n-2}n$. And the total number is just their sum.
I beg to differ. When the instructor and captain is the same there are $n.2^{n-1}$ choices and when they are different there are $\binom{n}{2}.2!.2^{n-2}$ choices. Since the cases are disjoint, the total number of choices are $2^{n-2}(2n+n^2-n)=n(n+1)2^{n-2}$.
বড় ভালবাসি তোমায়,মা

User avatar
Masum
Posts:592
Joined:Tue Dec 07, 2010 1:12 pm
Location:Dhaka,Bangladesh

Re: Putnam, 1962: Summing Binomials

Unread post by Masum » Wed Oct 31, 2012 11:30 pm

Yeah, you are right. Something was wrong, when I was writing the post.
One one thing is neutral in the universe, that is $0$.

User avatar
Masum
Posts:592
Joined:Tue Dec 07, 2010 1:12 pm
Location:Dhaka,Bangladesh

Re: Putnam, 1962: Summing Binomials

Unread post by Masum » Wed Oct 31, 2012 11:33 pm

Now, find the sum \[\sum_{i=0}^n\binom nii^3\]
The same trick should work. :)
One one thing is neutral in the universe, that is $0$.

Post Reply