# Duke Math Meet 2008 Problem 8 Solution (Individual Round)

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

Discussion:

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

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

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

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

Thus $$\sum_{k=1}^{2008} k \binom{2008}{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 \implies 2^{1728} \equiv 2^8 \equiv 56$$ mod 100.

Earlier we had $$2^{72} \equiv -4 \implies 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 \implies 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.