Wikipedia:Reference desk/Archives/Mathematics/2024 August 4

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

August 4

Even binomial coefficients

Is there an elementary way to show that all the entries except the outer two, on a row of Pascal's triangle corresponding to a power of 2, are even? 2A00:23C6:AA0D:F501:658A:3BC6:7F9D:2A4A (talk) 17:37, 4 August 2024 (UTC)

The entries in Pascal's triangle are the coefficients of aⁿb^n-i in (a+b)ⁿ. It's easy to see that (a+b)²=(a²+b²) mod 2, and consequently (a+b)⁴=(a⁴+b⁴) mod 2, (a+b)⁸=(a⁸+b⁸) mod 2, and in general (a+b)ⁿ=(aⁿ+bⁿ) mod 2 if n is a power of 2. This implies that all the coefficients of aⁿb^n-i are 0 mod 2 except when i=0 or i=n. Note, there are more complex formulas for finding aⁿb^n-i mod 2 or any other prime for any values of n and i. --RDBury (talk) 18:40, 4 August 2024 (UTC)

@RDBury: Did you mean aⁱb^n-i in the first sentence...? --CiaPan (talk) 09:44, 5 August 2024 (UTC)

Yes, good catch. RDBury (talk) 13:20, 5 August 2024 (UTC)

Another way to see it is, we divide $2^{n}$ into two equal piles of size $2^{n-1}$, so that to select k things from $2^{n}$ is to select i things from one pile and k-i things from the other. That is, we have the following special case of Vandermonde's identity:

${\binom {2^{n}}{k}}=\sum _{i=0}^{k}{\binom {2^{n-1}}{i}}{\binom {2^{n-1}}{k-i}}$

In the right-hand side, every term appears twice, except the middle term (if k is even). We thus have

${\binom {2^{n}}{2k}}\equiv {\binom {2^{n-1}}{k}}{\pmod {2}}.$

We iterate this until k is either odd (and the right hand side is even by induction), or $n=0$ in which case $k=2^{n}$ or $k=0$, which corresponds one of the two outer binomial coefficients. Tito Omburo (talk) 18:51, 4 August 2024 (UTC)

(OP) I think the first approach more my level, but thanks to both for the replies.2A00:23C6:AA0D:F501:6CF2:A683:CAFC:3D8 (talk) 07:10, 5 August 2024 (UTC)