Maths Olympiad Prep

Library / /11 of 42

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 degn\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=0naixij=0nbjxj=i=0naibjxi+j=k=02n(i+j=kaibj)xk=k=02n(i=0kaibki)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)=(1x)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)(nki))xk=p(x)q(x)=(1x2)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 0k2n0 \le k \le 2n,
i=0k(1)i(ni)(nki)={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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.