Alternating sum of combinatorics

Question

I have tried to do this exercise using index degradation, using Newton's binomial, if you can give me some idea to solve this problem I will appreciate

Let $a,b\in\mathbb{Z}^+$ such that $${1999 \choose 0}-{1999 \choose 2}+{1999 \choose 4}-\dots-{1999 \choose 1998}=a^b$$ the question is to find the smallest value of $a+b$.

Answer 1

Visualization

I will first explain how to visualize the back propagation of Pascal's identity, just in case you haven't seen this method before. Let's look at these identities graphically on Pascal's triangle:

Pascal's identity: $$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$$

Whenever we see a number in Pascal's triangle, we know that it is the sum of the two numbers above it. For the purposes of this visualization, if you see a number inside the circle, it represents the multiplier of that particular binomial coefficient.

Finally, don't forget that the triangle is symmetrical. Symmetric identity: $$\binom{n}{k} = \binom{n}{n-k}$$

Proof

Apply Pascal's identity. Notice that each row has the same sum. Just to make it easier to see, positive multipliers are green and negative multipliers are red.

Notice two patterns:

• Every time we back propagate two rows, the multiplier is doubled.
• (Remember also that due to the symmetric identity, it is valid to start from the right instead of the left.) If there are the same amount of green and red circles on a particular row, then the signs of the multipliers two rows back are flipped. So if the initial row started $+$, $-$, etc., then two rows back it will start $-$, $+$, etc.

So if we are trying to find:

$${1999 \choose 0}-{1999 \choose 2}+{1999 \choose 4}-\cdots-{1999 \choose 1998}$$

then we know this is equal to:

$$-4\left[{1995 \choose 0}-{1995 \choose 2}+{1995 \choose 4}-\dots-{1995 \choose 1994}\right]$$

which is equal to:

$$(-4)^2 \left[{1991 \choose 0}-{1991 \choose 2}+{1991 \choose 4}-\dots-{1991 \choose 1990}\right]$$

We can keep doing this until we get: $$(-4)^{499} \left[{3 \choose 0}-{3 \choose 2}\right]$$

which now becomes very easy to simplify to $2^{999}$.

Reflection

Try to see how this recursion pattern is parallel to the technique where you find the real part of $(1+i)^{1999}$ by converting $1+i$ to polar form and looking at the pattern when multiplying/dividing by $(1+i)^4$.

In my opinion, this proof is a little bit more obtuse and not as elegant as the $(1+i)^{1999}$ method, but I think there is value to knowing this technique. It is a fairly straightforward strategy without any need to invoke derivatives or constructing a counting proof, which makes it an excellent "last resort" or "brute force" strategy.