Count Them Differently

For discussing Olympiad Level Combinatorics problems
User avatar
Masum
Posts:592
Joined:Tue Dec 07, 2010 1:12 pm
Location:Dhaka,Bangladesh
Count Them Differently

Unread post by Masum » Wed Jan 09, 2013 1:31 am

Find a combinatorial proof of the following theorem known from বাচ্চাকাল।
\[1^2+2^2+\ldots+n^2=\binom {n+2}3+\binom{n+1}3\]
এইটা আমার বাইর করা প্রথম কম্বিনেটরিয়াল প্রুফ। তারপরে আমি যাই দেখি তারই কম্বিনেটরিয়াল প্রুফ বাইর করার ইচ্ছা হইত। ও আর এইটা আমারে চমক ভাই দিছিল।
One one thing is neutral in the universe, that is $0$.

User avatar
zadid xcalibured
Posts:217
Joined:Thu Oct 27, 2011 11:04 am
Location:mymensingh

Re: Count Them Differently

Unread post by zadid xcalibured » Wed Jan 09, 2013 9:18 pm

$$\binom{k}{1}+2\binom{k}{2}=k+2\frac{k\left( k-1\right) }{2}=k^{2} $$

we get

$\sum_{k=1}^{n}k^{2}=\sum_{k=0}^{n}\binom{k}{1}+2\binom{k}{2}% =\sum_{i=1}^{n}\binom{k}{1}+2\sum_{k=1}^{n}\binom{k}{2} \\ &=&\binom{n+1}{2}+2\binom{n+1}{3} \\ &=&\frac{n\left( n+1\right) \left( 2n+1\right) }{6}$

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

Re: Count Them Differently

Unread post by Masum » Thu Jan 10, 2013 2:34 pm

I meant actually something like bijection or counting in two ways. I don't see the counting argument. :)
One one thing is neutral in the universe, that is $0$.

Post Reply