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

{| width = "100%"

|- ! colspan="3" align="center" | Mathematics desk |- ! width="20%" align="left" | < August 3 ! width="25%" align="center"|<< Jul | August | Sep >> ! width="20%" align="right" |Current desk > |}

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)

Template:Re 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:

$(\genfrac{}{}{0ex}{}{2^n}{k})=\sum _{i=0}^k(\genfrac{}{}{0ex}{}{2^{n-1}}{i})(\genfrac{}{}{0ex}{}{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

$(\genfrac{}{}{0ex}{}{2^n}{2k})\equiv (\genfrac{}{}{0ex}{}{2^{n-1}}{k})(\mathrm{mod}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)