Find the value of $\binom{2000}{2} + \binom{2000}{5} + \binom{2000}{8} + \cdots \binom{2000}{2000}$

Solution 1:

Tools used:

• The identity ${n\choose i}={n-1\choose i}+{n-1\choose i-1}$
• The identity $\sum\limits_{i=0}^n{n\choose i}=2^n$

Let $A(n,k)$ denote the sum of the binomial coefficients ${n\choose i}$ over every $0\leqslant i\leqslant n$ such that $i=k\bmod 3$, then we are after $$A(2000,2)$$ The identity ${n\choose i}={n-1\choose i}+{n-1\choose i-1}$ implies that, for every $n\geqslant1$, $$A(n,k)=A(n-1,k)+A(n-1,k-1)=\left(\sum_{j=0}^2A(n-1,j)\right)-A(n-1,k+1)$$ For every $n\geqslant0$, $$\sum_{j=0}^2A(n,j)=\sum_{i=0}^n{n\choose i}=2^n$$ hence

$$A(n,k)=2^{n-1}-A(n-1,k+1)$$

Iterating this, one gets $$A(n,k)=\left(2^{n-1}-2^{n-2}+\cdots+(-1)^{n-1}2^0\right)+(-1)^nA(0,k+n)$$ that is, evaluating the alternating sum in the parenthesis, $$A(n,k)=\tfrac13\cdot(2^n-(-1)^n)+(-1)^nA(0,k+n)$$ Recall that ${0\choose 0}=1$ while ${0\choose i}=0$ for every $i\ne0$ hence $A(0,k)=1$ if $k=0\bmod 3$ and $A(0,k)=0$ otherwise, which yields our final formula for $A(n,k)$ as

$$A(n,k)=\tfrac13\cdot(2^n-(-1)^n)+(-1)^n\cdot\mathbf 1_{n+k=0\bmod 3}$$

For example, $2000+2\ne0\bmod 3$ and $2000=0\bmod 2$ hence

$$A(2000,2)=\tfrac13\cdot\left(2^{2000}-1\right)$$

while $2000+0\ne0\bmod 3$ and $2000+1=0\bmod 3$ hence $$A(2000,0)=\tfrac13\cdot\left(2^{2000}-1\right)\qquad A(2000,1)=\tfrac13\cdot\left(2^{2000}+2\right)$$

Solution 2:

Try this. If $\omega$ is one of the complex cube roots of $1$ so that $\omega^3=1$ and $1+\omega+\omega^2=0$, consider the binomial expansion of $$(1+1)^{2000}+\omega(1+\omega)^{2000}+\omega^2(1+\omega^2)^{2000}$$which looks to me to come to three times your sum. Using $1+\omega=-\omega^2$ and $1+\omega^2=-\omega$ this becomes also $$2^{2000}+\omega^{4001}+\omega^{2002}=2^{2000}-1$$ so that the sum is $$\frac {2^{2000}-1}3$$

It has been pointed out in the comments that this isn't properly an answer to the question, as it uses complex numbers - and that is fair enough, and I don't expect lots of votes for this, which others may have posted if they had not read the comments which I didn't. Did's answer does a great job.

However, I wanted to leave this up in case a latecomer looking at the question might be interested in how this roots of unity approach works. When it is alternate terms it is just about $\pm 1$ and no-one comments that it is difficult. I mean adding/subtracting $(1+1)^n$ and $(1-1)^n$ to pick out the sums of odd and even terms.

Did's approach ultimately works for all such sums - it is clear that all the engineering is in place. I think the roots of unity approach is more economical as the gaps get bigger and is easier to express generally - I would say that is one reason it is more used.

Personally, I think of the roots of unity as twisting the sum (other geometric intuitions exist). Also I become more convinced, as time goes on, that understanding such "twisted sums" makes it much easier to get underneath things like Dirichlet's theorem on primes in arithmetic progression, and what might motivate a proof of that. So I believe it is worth the work to explore and understand this approach.

Solution 3:

Let $w=\exp(2\pi i/3)$. Then $w^3=1$ and $1+w+w^2=0$, and hence $$ (1+1)^{2000}+w(1+w)^{2000}+w^2(1+w^2)^{2000}\\=\sum_{k=0}^{2000}\Bigg(\binom{2000}{k}+\binom{2000}{k}w^{k+1}+\binom{2000}{k}w^{2k+2}\Bigg) \\=3 \Bigg(\binom{2000}{2}+\binom{2000}{5}+\cdots+\binom{2000 }{2000}\Bigg), $$ since $$ 1+w^{k+1}+w^{2k+2}=\left\{\begin{array}{ccc} 3 & \text{if} & k=2\mod 3,\\ 0 & \text{if} & k\ne2\mod 3. \end{array} \right. $$

Next $$ 1+w=-w^2\quad\Rightarrow\quad(1+w)^{2000}=w^{4000}=w\\ 1+w^2=-w\quad\Rightarrow\quad(1+w^2)^{2000}=w^{2000}=w^2 $$ Finally $$ (1+1)^{2000}+w(1+w)^{2000}+w^2(1+w^2)^{2000}=2^{2000}+w+w^2=2^{2000}-1. $$ Hence $$ \binom{2000}{2}+\binom{2000}{5}+\cdots+\binom{2000 }{2000}=\frac{1}{3}\big(2^{2000}-1\big) $$

Solution 4:

For $n\ge0$ let $$a_n=\binom n0+\binom n3+\binom n6+\cdots=\sum_{k=0}^\infty\binom n{3k},$$ $$b_n=\binom n1+\binom n4+\binom n7+\cdots=\sum_{k=0}^\infty\binom n{3k+1},$$ $$c_n=\binom n2+\binom n5+\binom n8+\cdots=\sum_{k=0}^\infty\binom n{3k+2};$$ we seek the value of $c_{2000}.$ Observe that $$a_n+b_n+c_n=2^n$$ and, for $n\ge1,$ from Pascal's rule we get the recurrences $$a_n=a_{n-1}+c_{n-1},$$ $$b_n=a_{n-1}+b_{n-1},$$ $$c_n=b_{n-1}+c_{n-1}.$$ Hence, for $n\ge3,$ we have $$c_n=b_{n-1}+c_{n-1}=a_{n-2}+2b_{n-2}+c_{n-2}=3a_{n-3}+3b_{n-3}+2c_{n-3}$$ $$=3(a_{n-3}+b_{n-3}+c_{n-3})-c_{n-3}=3\cdot2^{n-3}-c_{n-3}$$ and, for $n\ge6,$ $$c_n=3\cdot2^{n-3}-c_{n-3}=3\cdot2^{n-3}-(3\cdot2^{n-6}-c_{n-6})=c_{n-6}+21\cdot2^{n-6},$$ that is: $$\boxed{c_n=c_{n-6}+21\cdot2^{n-6}}$$ Since $2000\equiv2\pmod6,$ we establish a closed formula for this case, namely $$\boxed{c_n=\frac{2^n-1}3\text{ when }n\equiv2\pmod6}\ ,$$ by induction.

$c_2=\binom22=1=\frac{2^2-1}3.$

If $c_n=\frac{2^n-1}3,$ then $$c_{n+6}=c_n+21\cdot2^n=\frac{2^n-1}3+21\cdot2^n=\frac{2^{n+6}-1}3.$$ In particular, when $n=2000,$ we have: $$\boxed{\sum_{k=0}^\infty\binom{2000}{3k+2}=\sum_{k=0}^{666}\binom{2000}{3k+2}=c_{2000}=\frac{2^{2000}-1}3}$$

By the way, since $c_0=0=\frac{2^0-1}3,$ the identity $c_n=\frac{2^n-1}3$ also holds when $n\equiv0\pmod6.$
The general formula is $$\boxed{\sum_{k=0}^\infty\binom n{3k+2}=\sum_{k=0}^{\left\lfloor\frac{n-2}3\right\rfloor}\binom n{3k+2}=c_n=\frac{2^n+2\cos\frac{(n+2)\pi}3}3}$$