Duke Math Meet 2008 Problem 8 Solution (Individual Round)

Let's try to find the solution to Duke Math Meet 2008 Problem 8. This question is from the individual round of that meet.

Problem: Duke Math Meet 2008 Problem 8

Find the last two digits of $ \sum_{k=1}^{2008} k {{2008}\choose{k}} $

Discussion:

$ (1+x)^n = \sum_{k=0}^{n} {{n}\choose{k}}x^k $

We differentiate both sides to have $ n(1+x)^{n-1} = \sum_{k=1}^{n} k {{n}\choose{k}}x^{k-1} $

Put $ n=2008 $ and $ x=1$ in the above equation to have

$ 2008(1+1)^{2007} = \sum_{k=1}^{2008} k {{2008}\choose{k}}1^{k-1} $

Thus $ \sum_{k=1}^{2008} k {{2008}\choose{k}} = 2^{2007} \times 2008 \equiv 8 \times 2^{2007} \equiv 2^{2010} $ mod 100

Now $ 2^{12} = 4096 \equiv -4 $ mod 100 . Now raising both sides to the power of 6, we have $ 2^{72} \equiv (-4)^6 \equiv 2^{12} \equiv -4 $mod 100 . Again raising both sides to the power 6 we have $ 2^{432} \equiv -4 \Rightarrow 2^{1728} \equiv 2^8 \equiv 56 $ mod 100.

Earlier we had $ 2^{72} \equiv -4 \Rightarrow 2^{216} \equiv -64 \equiv 36 $ mod 100

Hence $ 2^{1728} \times 2^{216} \equiv 2^{1944} \equiv 56 \times 36 \equiv 16 $ mod 100

Finally we know $ 2^{12} \equiv -4 \Rightarrow 2^{60} \equiv -1024 \equiv 76 $ mod 100 . Hence $ 2^{1944} \times 2^{60} \equiv 2^{2004} \equiv 16 \times 76 \equiv 1216 \equiv 16 $ mod 100

Thus $ 2^{2004} \times 2^{6} \equiv 2^{2010} \equiv 16 \times 64 \equiv 1024 \equiv 24 $ mod 100.

The two digits are 24.

Some Useful Links:

• Duke Math Meet 2009 Problem 9
• Our Math Olympiad Program
• AM-GM Inequality - Video