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

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

I've seen many complex proofs. I am looking for an elementary proof. I know the fact that $\binom{2000}{0} + \binom{2000}{1} + \binom{2000}{2} + \cdots \binom{2000}{2000} = 2^{2000}$. This may help here.

• Do you know the binomial theorem?
– DKS
Commented Feb 9, 2017 at 14:50
• @DKS Yes ! :| :| Commented Feb 9, 2017 at 14:50
• So, proofs involving complex numbers are not allowed? Commented Feb 9, 2017 at 14:51
• What is the pattern of the sequence? $(2,5,8,\ldots,2000)$ does not really make it clear how the $\ldots$ part goes. Commented Feb 9, 2017 at 14:52
• If complex numbers are forbidden please add this to the question. If you want a combinatorial proof please ask for one. Commented Feb 9, 2017 at 17:18

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)$$

• This is nicely done! Commented Feb 9, 2017 at 18:13
• I have added some comments to my (not really an) answer (having now had a bit of time to think). I though of commenting more on yours when I was on a walk earlier, but you seem to have said all that is necessary. Commented Feb 9, 2017 at 22:06

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.

• Quote: "So, proofs involving complex numbers are not allowed? – S.C.B. 2 hours ago @S.C.B. No... I think they are not elementary – Rezwan Arefin 2 hours ago"
– Did
Commented Feb 9, 2017 at 17:14
• @Did Sorry, I just read the question which said that "complex" proofs were not allowed, not complex numbers.. I think this is the neatest way to do it. Commented Feb 9, 2017 at 17:17

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)$$

• Could you expand a little on how $(1+1)^{2000} + w(1+w)^{2000} + w^2(1+w^2)^{2000}$ has the expansion given above? Other than writing out a large number of terms, I'm not sure how I'd recognize that. Commented Feb 11, 2017 at 2:04
• @apnorton See my edited answer. Commented Feb 11, 2017 at 18:13

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}$$