Maths Olympiad Prep

Library / IRL ABooklet /54 of 191

IRL ABooklet

Algebra Difficulty 5.4 AIME, harder Prove it Ireland

Prove that
B=∑k=0n(−1)k(nk)2={0,if n is odd,(−1)n2(nn2),if n is even. B = \sum_{k=0}^{n} (-1)^k \binom{n}{k}^2 = \begin{cases} 0, & \text{if } n \text{ is odd,} \\ (-1)^{\frac{n}{2}} \binom{n}{\frac{n}{2}}, & \text{if } n \text{ is even.} \end{cases}

Solution

If p,qp, q are polynomials of deg⁡≤n\deg \le n with coefficients ak,bka_k, b_k respectively, then the coefficients of the product pqpq may be found in terms of those of pp and qq as follows:
p(x)q(x)=∑i=0naixi∑j=0nbjxj=∑i=0naibjxi+j=∑k=02n(∑i+j=kaibj)xk=∑k=02n(∑i=0kaibk−i)xk \begin{aligned} p(x)q(x) &= \sum_{i=0}^{n} a_i x^i \sum_{j=0}^{n} b_j x^j = \sum_{i=0}^{n} a_i b_j x^{i+j} \\ &= \sum_{k=0}^{2n} \left( \sum_{i+j=k} a_i b_j \right) x^k = \sum_{k=0}^{2n} \left( \sum_{i=0}^{k} a_i b_{k-i} \right) x^k \end{aligned}

To obtain expression BB, apply this formula with
p(x)=(1+x)n=∑k=0n(nk)xkandq(x)=(1−x)n=∑k=0n(−1)k(nk)xk. p(x) = (1 + x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k \quad \text{and} \quad q(x) = (1 - x)^n = \sum_{k=0}^{n} (-1)^k \binom{n}{k} x^k.
Then
∑k=02n(∑i=0k(−1)i(ni)(nk−i))xk=p(x)q(x)=(1−x2)n=∑r=0n(−1)r(nr)x2r, \sum_{k=0}^{2n} \left( \sum_{i=0}^{k} (-1)^i \binom{n}{i} \binom{n}{k-i} \right) x^k = p(x)q(x) = (1-x^2)^n = \sum_{r=0}^{n} (-1)^r \binom{n}{r} x^{2r},
so that, comparing coefficients, we see that, if 0≤k≤2n0 \le k \le 2n,
∑i=0k(−1)i(ni)(nk−i)={0,if k is odd,(−1)k2(nk2),if k is even. \sum_{i=0}^{k} (-1)^i \binom{n}{i} \binom{n}{k-i} = \begin{cases} 0, & \text{if } k \text{ is odd,} \\ (-1)^{\frac{k}{2}} \binom{n}{\frac{k}{2}}, & \text{if } k \text{ is even.} \end{cases}
In particular, taking k=nk = n,
B=∑k=0n(−1)k(nk)2={0,if n is odd,(−1)n2(nn2),if n is even. B = \sum_{k=0}^{n} (-1)^k \binom{n}{k}^2 = \begin{cases} 0, & \text{if } n \text{ is odd,} \\ (-1)^{\frac{n}{2}} \binom{n}{\frac{n}{2}}, & \text{if } n \text{ is even.} \end{cases}

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.