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 Feb 9 '17 at 14:50
• @DKS Yes ! :| :| – Rezwan Arefin Feb 9 '17 at 14:50
• So, proofs involving complex numbers are not allowed? – S.C.B. Feb 9 '17 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. – Henning Makholm Feb 9 '17 at 14:52
• If complex numbers are forbidden please add this to the question. If you want a combinatorial proof please ask for one. – Mark Bennet Feb 9 '17 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! – Mark Bennet Feb 9 '17 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. – Mark Bennet Feb 9 '17 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 Feb 9 '17 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. – Mark Bennet Feb 9 '17 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. – apnorton Feb 11 '17 at 2:04
• @apnorton See my edited answer. – Yiorgos S. Smyrlis Feb 11 '17 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}$$