Calculating a sum of binomial coefficients

Question

I am seeking assistance in calculating the sum of a specific sequence of binomial coefficients: $1000 \choose 1$ + $1000 \choose 5$ + $1000 \choose 9$ + ... + $1000 \choose 997$. I have noticed that the terms in the sum follow the pattern $\sum_{k=0}^{249} \binom{1000}{4k+1}$. However, I am uncertain about the next steps in simplifying this expression. I am wondering if using the properties of binomial coefficients could be helpful. I have also attempted to use Vandermonde's identity, but I haven't been able to simplify the expression significantly.

Could someone provide guidance on which properties of binomial coefficients to apply or suggest an approach to calculate the sum effectively?

Answer 1

Notice that ${1000\choose997} = {1000\choose3}$. You can rewrite your sum as

$$\sum_{k=0}^{249} {1000\choose 2k+1}$$

Which is half of the odd terms of that row of Pascal's triangle. There are standard exercises to show that the sum of the all the odd terms is $2^{999}$, so your sum should be half of that $2^{998}.$

Answer 2

Consider the expansion of $f(x)=(1 + x)^{1000}$ using the binomial theorem:

$$f(x)=(1 + x)^{1000} = \binom{1000}{0} + \binom{1000}{1}x + \\ \binom{1000}{2}x^2 + \binom{1000}{3}x^3 + \binom{1000}{4}x^4 + \ldots + \binom{1000}{1000}x^{1000}$$

We evaluate $f(x)$ at $i, i^2=-1,i^3=-i,i^4=1$, respectively. \begin{align} f(i) &= 1\cdot\left[ \binom{1000}{0}+\binom{1000}{4}+\dots+\binom{1000}{1000}\right] \\ &+i\cdot\left[ \binom{1000}{1}+\binom{1000}{5}+\dots+\binom{1000}{997}\right]\\ &-1\cdot\left[ \binom{1000}{2}+\binom{1000}{6}+\dots+\binom{1000}{998}\right]\\ &-i\cdot\left[ \binom{1000}{3}+\binom{1000}{7}+\dots+\binom{1000}{999}\right]\\ f(-1) &= 1\cdot\left[ \binom{1000}{0}+\binom{1000}{4}+\dots+\binom{1000}{1000}\right] \\ &-1\cdot\left[ \binom{1000}{1}+\binom{1000}{5}+\dots+\binom{1000}{997}\right]\\ &+1\cdot\left[ \binom{1000}{2}+\binom{1000}{6}+\dots+\binom{1000}{998}\right]\\ &-1\cdot\left[ \binom{1000}{3}+\binom{1000}{7}+\dots+\binom{1000}{999}\right]\\ f(-i) &= 1\cdot\left[ \binom{1000}{0}+\binom{1000}{4}+\dots+\binom{1000}{1000}\right] \\ &-i\cdot\left[ \binom{1000}{1}+\binom{1000}{5}+\dots+\binom{1000}{997}\right]\\ &-1\cdot\left[ \binom{1000}{2}+\binom{1000}{6}+\dots+\binom{1000}{998}\right]\\ &+i\cdot\left[ \binom{1000}{3}+\binom{1000}{7}+\dots+\binom{1000}{999}\right]\\ f(1) &= 1\cdot\left[ \binom{1000}{0}+\binom{1000}{4}+\dots+\binom{1000}{1000}\right] \\ &+1\cdot\left[ \binom{1000}{1}+\binom{1000}{5}+\dots+\binom{1000}{997}\right]\\ &+1\cdot\left[ \binom{1000}{2}+\binom{1000}{6}+\dots+\binom{1000}{998}\right]\\ &+1\cdot\left[ \binom{1000}{3}+\binom{1000}{7}+\dots+\binom{1000}{999}\right]\\ \end{align} Let \begin{align} a&=\left[ \binom{1000}{0}+\binom{1000}{4}+\dots+\binom{1000}{1000}\right]\\ b&=\left[ \binom{1000}{1}+\binom{1000}{5}+\dots+\binom{1000}{997}\right]\\ c&=\left[ \binom{1000}{2}+\binom{1000}{6}+\dots+\binom{1000}{998}\right]\\ d&=\left[ \binom{1000}{3}+\binom{1000}{7}+\dots+\binom{1000}{999}\right]\\ \end{align} where $b$ is our desired result. We have \begin{align} a+ib-c-id&=f(i) \\ a-b+c-d&=f(-1)\\ a-ib-c+id&=f(-i)\\ a+b+c+d&=f(1)\\ \end{align} Solving these linear equations, we get \begin{align} b &= \frac{1}{4}\left[-i\cdot f(i)-f(-1)+i\cdot f(-i)+f(1)\right]\\ &= \frac{1}{4}\left[-i\cdot (1+i)^{1000}+i\cdot (1-i)^{1000}+2^{1000}\right]\\ \end{align} where we have $(1+i)^2=2i,(1-i)^2=-2i$. So $$(1+i)^{1000}=(1-i)^{1000}=2^{500}$$ Finally, $$b = \frac{1}{4}\cdot 2^{1000}=2^{998}$$