2
$\begingroup$

I came across the following sum online and have spent awhile trying to compute it: $$\sum_{i=0}^{100} \binom{300}{3i}$$ Based on a pattern I noticed, the answer should be $\frac{2^{300}}{3}$ rounded up. However I cannot figure out how to actually solve for the answer. The problem gave the hint of using the binomial theorem: $(a+b)^n=\sum_{k=0}^{n} \binom{n}{k} a^{k} b^{n-k}$. For example, the problem before it was $\sum_{i=0}^{100} \binom{100}{i}$ which would just end up being $$\sum_{i=0}^{100} \binom{100}{i}=\sum_{i=0}^{100} \binom{100}{i}1^{k} 1^{100-k}=(1+1)^{100}=2^{100}.$$ The $3i$ in the denominator is the real issue here because I can't seem to manipulate it to resemble the binomial theorem. I have even tried expanding it out to look for patterns but to no avail. Anyone have any hints or tips?

$\endgroup$
6
$\begingroup$

Hints:

  • Consider the function $f(x):=\sum_{i=0}^{300}\limits\binom{300}{i}x^i=(1+x)^{300}$
  • Consider the value of $\frac 13\left(f(1)+f(\omega)+f(\omega^2)\right)$ where $\omega$ denotes a primitive cube root of unity.
  • Recall that $1+\omega^n+\omega^{2n}=\begin{cases}0~\forall~n\not\equiv 0\pmod3\\ 3~\forall~n\equiv 0\pmod3\end{cases}$

Added a generalization:

Notice that if you go a way further, you can generalize this problem. Consider positive integers $n$ and $d$ such that $d\leq n$.

You can generalize the above problem, i.e., compute the sum $\displaystyle\mathcal{S}(n,d)=\sum\limits_{i=0}^{\lfloor n/d\rfloor}\dbinom{n}{di}$

For this, you would be considering $f(x):=\sum\limits_{i=0}^n\binom{n}{i}x^i=(1+x)^n$ and we'll have,

$$\mathcal{S}(n,d)=\frac 1d\sum_{i=0}^{d-1}f(\omega^i)$$

where $\omega$ denotes a primitive $d^{\textrm{th}}$ root of unity.

A result used to write the above expression for $\mathcal{S}(n,d)$ is,

$$\sum_{i=0}^{d-1}\omega^{ik}=\begin{cases}0~\forall~k\not\equiv 0\pmod{d}\\ d~\forall~k\equiv 0\pmod{d}\end{cases}$$

The problem at hand would be just computing $\mathcal{S}(300,3)$.

$\endgroup$
  • 1
    $\begingroup$ Is the index in $f(x)$ supposed to be an $i$ or $n$? $\endgroup$ – MBP Nov 25 '15 at 22:08
  • $\begingroup$ @MatthewPereira, typo fixed! :) $\endgroup$ – Prasun Biswas Nov 25 '15 at 22:09
  • 1
    $\begingroup$ @MatthewPereira, check it out, I added a generalization. $\endgroup$ – Prasun Biswas Nov 25 '15 at 22:28
  • $\begingroup$ I'm currently looking over the first part, trying to see how it helps. I'm not really familiar with roots of unity. Thanks! $\endgroup$ – MBP Nov 25 '15 at 22:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.