Skip to main content
MathOverflow

Return to Answer

fix mistake in indexing the sum for $F$, and also correct two minor typos (missing ")", and \cdots for \ldots)
Source Link
Noam D. Elkies
Noam D. Elkies
  • 79.9k
  • 15
  • 281
  • 376

Apparently not mentioned yet, though surely not new: use the quadratic equation satisfied by the generating function. Since we look for $n+1$ to be a power of $2$, we shift the index by $1$ and consider $$ F = \sum_{n=1}^\infty C_{n+1} x^n = x + x^2 + 2 x^3 + 5 x^4 + 14 x^5 + 42 x^6 + 132 x^7 + 429 x^8 + \cdots. $$$$ F = \sum_{n=0}^\infty C_n x^{n+1} = x + x^2 + 2 x^3 + 5 x^4 + 14 x^5 + 42 x^6 + 132 x^7 + 429 x^8 + \cdots. $$ Then $F = x + F^2$. Instead of solving this quadratic equation, apply it recursively ${} \bmod 2$. Recall that for each $r=1,2,3,\cdots$$r=1,2,3,\ldots$ we have the congruence $(a+b)^{2^r} \equiv a^{2^r} + b^{2^r} \bmod 2$ (proof: induction, the case $r=1$ being $(a+b)^2 = a^2 + 2ab + b^2 \equiv a^2+b^2$). We obtain: $$ \begin{array}{rl} F \; = \!\! & x + F^2 \cr = \!\! & x + (x+F^2)^2 \equiv x + x^2 + F^4 \cr = \!\! & x + x^2 + (x+F^2)^4 \equiv x + x^2 + x^4 + F^8 \cr = \!\! & x + x^2 + x^4 + (x+F^2)^8 \equiv x + x^2 + x^4 + x^8 + F^{16} \cr = \!\! & \cdots \cr \equiv \!\! & x + x^2 + x^4 + x^8 + x^{16} + x^{32} + x^{64} + \cdots \cr \end{array} $$ so indeed $C_n$ is odd if and only if $n+1$ is a power of $2$, QED.

Apparently not mentioned yet, though surely not new: use the quadratic equation satisfied by the generating function. Since we look for $n+1$ to be a power of $2$, we shift the index by $1$ and consider $$ F = \sum_{n=1}^\infty C_{n+1} x^n = x + x^2 + 2 x^3 + 5 x^4 + 14 x^5 + 42 x^6 + 132 x^7 + 429 x^8 + \cdots. $$ Then $F = x + F^2$. Instead of solving this quadratic equation, apply it recursively ${} \bmod 2$. Recall that for each $r=1,2,3,\cdots$ we have the congruence $(a+b)^{2^r} \equiv a^{2^r} + b^{2^r} \bmod 2$ (proof: induction, the case $r=1$ being $(a+b)^2 = a^2 + 2ab + b^2 \equiv a^2+b^2$. We obtain: $$ \begin{array}{rl} F \; = \!\! & x + F^2 \cr = \!\! & x + (x+F^2)^2 \equiv x + x^2 + F^4 \cr = \!\! & x + x^2 + (x+F^2)^4 \equiv x + x^2 + x^4 + F^8 \cr = \!\! & x + x^2 + x^4 + (x+F^2)^8 \equiv x + x^2 + x^4 + x^8 + F^{16} \cr = \!\! & \cdots \cr \equiv \!\! & x + x^2 + x^4 + x^8 + x^{16} + x^{32} + x^{64} + \cdots \cr \end{array} $$ so indeed $C_n$ is odd if and only if $n+1$ is a power of $2$, QED.

Apparently not mentioned yet, though surely not new: use the quadratic equation satisfied by the generating function. Since we look for $n+1$ to be a power of $2$, we shift the index by $1$ and consider $$ F = \sum_{n=0}^\infty C_n x^{n+1} = x + x^2 + 2 x^3 + 5 x^4 + 14 x^5 + 42 x^6 + 132 x^7 + 429 x^8 + \cdots. $$ Then $F = x + F^2$. Instead of solving this quadratic equation, apply it recursively ${} \bmod 2$. Recall that for each $r=1,2,3,\ldots$ we have the congruence $(a+b)^{2^r} \equiv a^{2^r} + b^{2^r} \bmod 2$ (proof: induction, the case $r=1$ being $(a+b)^2 = a^2 + 2ab + b^2 \equiv a^2+b^2$). We obtain: $$ \begin{array}{rl} F \; = \!\! & x + F^2 \cr = \!\! & x + (x+F^2)^2 \equiv x + x^2 + F^4 \cr = \!\! & x + x^2 + (x+F^2)^4 \equiv x + x^2 + x^4 + F^8 \cr = \!\! & x + x^2 + x^4 + (x+F^2)^8 \equiv x + x^2 + x^4 + x^8 + F^{16} \cr = \!\! & \cdots \cr \equiv \!\! & x + x^2 + x^4 + x^8 + x^{16} + x^{32} + x^{64} + \cdots \cr \end{array} $$ so indeed $C_n$ is odd if and only if $n+1$ is a power of $2$, QED.

Source Link
Noam D. Elkies
Noam D. Elkies
  • 79.9k
  • 15
  • 281
  • 376

Apparently not mentioned yet, though surely not new: use the quadratic equation satisfied by the generating function. Since we look for $n+1$ to be a power of $2$, we shift the index by $1$ and consider $$ F = \sum_{n=1}^\infty C_{n+1} x^n = x + x^2 + 2 x^3 + 5 x^4 + 14 x^5 + 42 x^6 + 132 x^7 + 429 x^8 + \cdots. $$ Then $F = x + F^2$. Instead of solving this quadratic equation, apply it recursively ${} \bmod 2$. Recall that for each $r=1,2,3,\cdots$ we have the congruence $(a+b)^{2^r} \equiv a^{2^r} + b^{2^r} \bmod 2$ (proof: induction, the case $r=1$ being $(a+b)^2 = a^2 + 2ab + b^2 \equiv a^2+b^2$. We obtain: $$ \begin{array}{rl} F \; = \!\! & x + F^2 \cr = \!\! & x + (x+F^2)^2 \equiv x + x^2 + F^4 \cr = \!\! & x + x^2 + (x+F^2)^4 \equiv x + x^2 + x^4 + F^8 \cr = \!\! & x + x^2 + x^4 + (x+F^2)^8 \equiv x + x^2 + x^4 + x^8 + F^{16} \cr = \!\! & \cdots \cr \equiv \!\! & x + x^2 + x^4 + x^8 + x^{16} + x^{32} + x^{64} + \cdots \cr \end{array} $$ so indeed $C_n$ is odd if and only if $n+1$ is a power of $2$, QED.