Find the number of even numbers among the following 1001 numbers: \(\left( \begin{matrix} 1000 \\ 0 \end{matrix} \right) ,\left( \begin{matrix} 1000 \\ 1 \end{matrix} \right) ,\left( \begin{matrix} 1000 \\ 2 \end{matrix} \right) ,\left( \begin{matrix} 1000 \\ 3 \end{matrix} \right) ,\left( \begin{matrix} 1000 \\ 4 \end{matrix} \right) . . . \left( \begin{matrix} 1000 \\ 1000 \end{matrix} \right) \).

## Comments

Sort by:

TopNewestIt is probably easiest to use a consequence of Lucas's theorem. Since the base 2 expansion of \(1000\) is \(1111101000,\) those values \(n\) between \(0\) and \(1000\) inclusive that have a \(1\) in their base 2 expansion in at least one place where the expansion of \(1000\) has a \(0\) will render \(\binom{1000}{m}\) even.

Now it will be easier to count the complement here, i.e., the number of values which have \(0\)'s in their binary expansion wherever the binary expansion of \(1000\) does, and then subtract this from \(1001.\) So after fixing the four \(0\)'s in place, we have six other digit positions which can be filled by either a \(0\) or a \(1.\) Thus there will be \(2^{6} = 64\) values \(m\) which will render \(\binom{1000}{m}\) odd, and thus there are \(1001 - 64 = 937\) numbers in the given list that are even. – Brian Charlesworth · 2 years, 2 months ago

Log in to reply

– Rohit Ner · 2 years, 2 months ago

Thank you sir for posting such a beautiful approach! Please let me know if there is any alternative method as many jee aspirants are unaware of Lucas theorem. :)Log in to reply

– Brian Charlesworth · 2 years, 2 months ago

You're welcome. :) Yes, I noticed the JEE hashtag and wondered if this was a suitable approach for that exam, but I don't know of any other way of solving this problem without resorting to brute force. I'll be interested to see if anyone else knows of a JEE-friendly method.Log in to reply

– Rohit Ner · 2 years, 2 months ago

Can you help me finding the value of : \[\huge\sum _{ r=0 }^{ n }{ \frac { { \left( -1 \right) }^{ r } }{ \left( \begin{matrix} n \\ r \end{matrix} \right) } } \]Log in to reply

Then if \(n\) is odd, we would also have \((-1)^{r} = -((-1)^{n-r}),\) which would mean that all the terms in the sum would cancel pairwise, leaving us with an answer of \(0.\)

It gets more interesting if \(n\) is even. I found formula #34 in this link, which is complicated, but with \(p = 1\) it would appear to give a general solution of

\(S_{n} = (1 + (-1)^{n})\dfrac{(n + 1)}{n + 2}.\)

So for \(n\) odd we have \(S_{n} = 0\), (as found before), and for \(n\) even we have \(S_{n} = \dfrac{2(n + 1)}{n + 2}.\)

I found another excellent resource here which confirms this result, (and much more).

Great question; I've never encountered this type of sum before. :) – Brian Charlesworth · 2 years, 2 months ago

Log in to reply

– Rohit Ner · 2 years, 2 months ago

Thank you a lot for your help sir. :) .Log in to reply

question inspired by this last question of yours. I hope you don't mind. :) – Brian Charlesworth · 2 years, 2 months ago

I posted aLog in to reply

– Rohit Ner · 2 years, 2 months ago

Its a very good question sir! A pleasure to see a question inspired by me! :)Log in to reply

– Brian Charlesworth · 2 years, 2 months ago

I'm glad that you liked (and solved) it. :)Log in to reply