Skip to main content
MathOverflow

Return to Answer

deleted 4 characters in body
Source Link
Fedor Petrov
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 460

Yes, this is true. The idea is to get $n-1$ out of the sum as a multiple.

We have $$c_n=1+\sum_{m=1}^{n-1}m{n\choose m}m^{n-1-m}=c_n=1+\sum_{m=1}^{n-1}n{n-1\choose m-1}m^{n-1-m}$$$$c_n=1+\sum_{m=1}^{n-1}m{n\choose m}m^{n-1-m}=1+\sum_{m=1}^{n-1}n{n-1\choose m-1}m^{n-1-m}$$ We see that if $n$ is even, then $c_n$ is odd.

Now let $n>1$ be odd. Then proceed this way:$$c_n=1+n\sum_{m=1}^{n-1}{n-1\choose m-1}+n\sum_{m=2}^{n-2}{n-1\choose m-1}(m^{n-1-m}-1)\\=1+n(2^{n-1}-1)+n(n-1)\sum_{m=2}^{n-2}{n-2\choose m-2}\cdot \frac{m^{n-1-m}-1}{m-1}\\=:1+n(2^{n-1}-1)+n(n-1)A.$$ Modulo 2 we have $$\frac{m^{n-1-m}-1}{m-1}=1+m+\ldots+m^{n-m-2}\equiv 1+m(n-m-2)\equiv 1,$$ so $$ A\equiv \sum_{m=2}^{n-2} {n-2\choose m-2}=2^{n-2}-1-(n-2)\equiv 0\pmod 2. $$ Then $c_n=(1-n)+(n2^{n-1})+n(n-1)A$, and $1-n$ has 2-adic valuation strictly smaller than two other summands, thus $\nu_2(c_n)=\nu_2(1-n)$.

Yes, this is true. The idea is to get $n-1$ out of the sum as a multiple.

We have $$c_n=1+\sum_{m=1}^{n-1}m{n\choose m}m^{n-1-m}=c_n=1+\sum_{m=1}^{n-1}n{n-1\choose m-1}m^{n-1-m}$$ We see that if $n$ is even, then $c_n$ is odd.

Now let $n>1$ be odd. Then proceed this way:$$c_n=1+n\sum_{m=1}^{n-1}{n-1\choose m-1}+n\sum_{m=2}^{n-2}{n-1\choose m-1}(m^{n-1-m}-1)\\=1+n(2^{n-1}-1)+n(n-1)\sum_{m=2}^{n-2}{n-2\choose m-2}\cdot \frac{m^{n-1-m}-1}{m-1}\\=:1+n(2^{n-1}-1)+n(n-1)A.$$ Modulo 2 we have $$\frac{m^{n-1-m}-1}{m-1}=1+m+\ldots+m^{n-m-2}\equiv 1+m(n-m-2)\equiv 1,$$ so $$ A\equiv \sum_{m=2}^{n-2} {n-2\choose m-2}=2^{n-2}-1-(n-2)\equiv 0\pmod 2. $$ Then $c_n=(1-n)+(n2^{n-1})+n(n-1)A$, and $1-n$ has 2-adic valuation strictly smaller than two other summands, thus $\nu_2(c_n)=\nu_2(1-n)$.

Yes, this is true. The idea is to get $n-1$ out of the sum as a multiple.

We have $$c_n=1+\sum_{m=1}^{n-1}m{n\choose m}m^{n-1-m}=1+\sum_{m=1}^{n-1}n{n-1\choose m-1}m^{n-1-m}$$ We see that if $n$ is even, then $c_n$ is odd.

Now let $n>1$ be odd. Then proceed this way:$$c_n=1+n\sum_{m=1}^{n-1}{n-1\choose m-1}+n\sum_{m=2}^{n-2}{n-1\choose m-1}(m^{n-1-m}-1)\\=1+n(2^{n-1}-1)+n(n-1)\sum_{m=2}^{n-2}{n-2\choose m-2}\cdot \frac{m^{n-1-m}-1}{m-1}\\=:1+n(2^{n-1}-1)+n(n-1)A.$$ Modulo 2 we have $$\frac{m^{n-1-m}-1}{m-1}=1+m+\ldots+m^{n-m-2}\equiv 1+m(n-m-2)\equiv 1,$$ so $$ A\equiv \sum_{m=2}^{n-2} {n-2\choose m-2}=2^{n-2}-1-(n-2)\equiv 0\pmod 2. $$ Then $c_n=(1-n)+(n2^{n-1})+n(n-1)A$, and $1-n$ has 2-adic valuation strictly smaller than two other summands, thus $\nu_2(c_n)=\nu_2(1-n)$.

added 13 characters in body
Source Link
Fedor Petrov
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 460

Yes, this is true. Consider two casesThe idea is to get $n-1$ out of the sum as a multiple.

  1. Assume that $n$ is even. Then $$c_n=1+\sum_{m=1}^{n-1}m{n\choose m}m^{n-1-m}=c_n=1+\sum_{m=1}^{n-1}n{n-1\choose m-1}m^{n-1-m}$$ is indeed odd.

  2. Let $n>1$ be odd. Then $$c_n=1+n\sum_{m=1}^{n-1}{n-1\choose m-1}+n\sum_{m=2}^{n-2}{n-1\choose m-1}(m^{n-1-m}-1)\\=1+n(2^{n-1}-1)+n(n-1)\sum_{m=2}^{n-2}{n-2\choose m-2}\cdot \frac{m^{n-1-m}-1}{m-1}\\=:1+n(2^{n-1}-1)+n(n-1)A.$$ It already follows that $\nu_2(c_n)\geqslant \nu_2(n-1)$, since $c_n\equiv n\cdot 2^{n-1} \pmod {n-1}$, and $\nu_2(n-1)<n-1$. The equality $\nu_2(c_n)=\nu_2(n-1)$ is thus equivalent to $A$ being even. Modulo 2 we have $$\frac{m^{n-1-m}-1}{m-1}=1+m+\ldots+m^{n-m-2}\equiv 1+m(n-m-2)\equiv 1,$$ so $$ A\equiv \sum_{m=2}^{n-2} {n-2\choose m-2}=2^{n-2}-1-(n-2) $$ is indeed even.

We have $$c_n=1+\sum_{m=1}^{n-1}m{n\choose m}m^{n-1-m}=c_n=1+\sum_{m=1}^{n-1}n{n-1\choose m-1}m^{n-1-m}$$ We see that if $n$ is even, then $c_n$ is odd.

Now let $n>1$ be odd. Then proceed this way:$$c_n=1+n\sum_{m=1}^{n-1}{n-1\choose m-1}+n\sum_{m=2}^{n-2}{n-1\choose m-1}(m^{n-1-m}-1)\\=1+n(2^{n-1}-1)+n(n-1)\sum_{m=2}^{n-2}{n-2\choose m-2}\cdot \frac{m^{n-1-m}-1}{m-1}\\=:1+n(2^{n-1}-1)+n(n-1)A.$$ Modulo 2 we have $$\frac{m^{n-1-m}-1}{m-1}=1+m+\ldots+m^{n-m-2}\equiv 1+m(n-m-2)\equiv 1,$$ so $$ A\equiv \sum_{m=2}^{n-2} {n-2\choose m-2}=2^{n-2}-1-(n-2)\equiv 0\pmod 2. $$ Then $c_n=(1-n)+(n2^{n-1})+n(n-1)A$, and $1-n$ has 2-adic valuation strictly smaller than two other summands, thus $\nu_2(c_n)=\nu_2(1-n)$.

Yes. Consider two cases.

  1. Assume that $n$ is even. Then $$c_n=1+\sum_{m=1}^{n-1}m{n\choose m}m^{n-1-m}=c_n=1+\sum_{m=1}^{n-1}n{n-1\choose m-1}m^{n-1-m}$$ is indeed odd.

  2. Let $n>1$ be odd. Then $$c_n=1+n\sum_{m=1}^{n-1}{n-1\choose m-1}+n\sum_{m=2}^{n-2}{n-1\choose m-1}(m^{n-1-m}-1)\\=1+n(2^{n-1}-1)+n(n-1)\sum_{m=2}^{n-2}{n-2\choose m-2}\cdot \frac{m^{n-1-m}-1}{m-1}\\=:1+n(2^{n-1}-1)+n(n-1)A.$$ It already follows that $\nu_2(c_n)\geqslant \nu_2(n-1)$, since $c_n\equiv n\cdot 2^{n-1} \pmod {n-1}$, and $\nu_2(n-1)<n-1$. The equality $\nu_2(c_n)=\nu_2(n-1)$ is thus equivalent to $A$ being even. Modulo 2 we have $$\frac{m^{n-1-m}-1}{m-1}=1+m+\ldots+m^{n-m-2}\equiv 1+m(n-m-2)\equiv 1,$$ so $$ A\equiv \sum_{m=2}^{n-2} {n-2\choose m-2}=2^{n-2}-1-(n-2) $$ is indeed even.

Yes, this is true. The idea is to get $n-1$ out of the sum as a multiple.

We have $$c_n=1+\sum_{m=1}^{n-1}m{n\choose m}m^{n-1-m}=c_n=1+\sum_{m=1}^{n-1}n{n-1\choose m-1}m^{n-1-m}$$ We see that if $n$ is even, then $c_n$ is odd.

Now let $n>1$ be odd. Then proceed this way:$$c_n=1+n\sum_{m=1}^{n-1}{n-1\choose m-1}+n\sum_{m=2}^{n-2}{n-1\choose m-1}(m^{n-1-m}-1)\\=1+n(2^{n-1}-1)+n(n-1)\sum_{m=2}^{n-2}{n-2\choose m-2}\cdot \frac{m^{n-1-m}-1}{m-1}\\=:1+n(2^{n-1}-1)+n(n-1)A.$$ Modulo 2 we have $$\frac{m^{n-1-m}-1}{m-1}=1+m+\ldots+m^{n-m-2}\equiv 1+m(n-m-2)\equiv 1,$$ so $$ A\equiv \sum_{m=2}^{n-2} {n-2\choose m-2}=2^{n-2}-1-(n-2)\equiv 0\pmod 2. $$ Then $c_n=(1-n)+(n2^{n-1})+n(n-1)A$, and $1-n$ has 2-adic valuation strictly smaller than two other summands, thus $\nu_2(c_n)=\nu_2(1-n)$.

deleted 124 characters in body
Source Link
Fedor Petrov
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 460

Yes. Consider two cases.

  1. Assume that $n$ is even. Then $$c_n=1+\sum_{m=1}^{n-1}m{n\choose m}m^{n-1-m}=c_n=1+\sum_{m=1}^{n-1}n{n-1\choose m-1}m^{n-1-m}$$ is indeed odd.

  2. Let $n>1$ be odd. Then $$c_n=1+n\sum_{m=1}^{n-1}{n-1\choose m-1}+n\sum_{m=2}^{n-2}{n-1\choose m-1}(m^{n-1-m}-1)\\=1+n(2^{n-1}-1)+n(n-1)\sum_{m=2}^{n-2}{n-2\choose m-2}\cdot \frac{m^{n-1-m}-1}{m-1}\\=:1+n(2^{n-1}-1)+n(n-1)A.$$ It already follows that $\nu_2(c_n)\geqslant \nu_2(n-1)$, since $c_n\equiv n\cdot 2^{n-1} \pmod {n-1}$, and $\nu_2(n-1)<n-1$. The equality $\nu_2(c_n)=\nu_2(n-1)$ is thus equivalent to $A$ being even. Denote $n-2=s$ (so $s$ is odd) and $m-2=j$, we get $$ A=\sum_{j=0}^{s-2} {s\choose j}\cdot \frac{(j+2)^{s-j-1}-1}{j+1}. $$ Modulo 2 we have $$\frac{(j+2)^{s-j-1}-1}{j+1}=1+(j+2)+\ldots+(j+2)^{s-j-2}\equiv 1+(j+2)(s-j-2)\equiv 1,$$$$\frac{m^{n-1-m}-1}{m-1}=1+m+\ldots+m^{n-m-2}\equiv 1+m(n-m-2)\equiv 1,$$ so $$ A\equiv \sum_{j=0}^{s-2} {s\choose j}=2^{s-2}-s-1 $$$$ A\equiv \sum_{m=2}^{n-2} {n-2\choose m-2}=2^{n-2}-1-(n-2) $$ is indeed even.

Yes. Consider two cases.

  1. Assume that $n$ is even. Then $$c_n=1+\sum_{m=1}^{n-1}m{n\choose m}m^{n-1-m}=c_n=1+\sum_{m=1}^{n-1}n{n-1\choose m-1}m^{n-1-m}$$ is indeed odd.

  2. Let $n>1$ be odd. Then $$c_n=1+n\sum_{m=1}^{n-1}{n-1\choose m-1}+n\sum_{m=2}^{n-2}{n-1\choose m-1}(m^{n-1-m}-1)\\=1+n(2^{n-1}-1)+n(n-1)\sum_{m=2}^{n-2}{n-2\choose m-2}\cdot \frac{m^{n-1-m}-1}{m-1}\\=:1+n(2^{n-1}-1)+n(n-1)A.$$ It already follows that $\nu_2(c_n)\geqslant \nu_2(n-1)$, since $c_n\equiv n\cdot 2^{n-1} \pmod {n-1}$, and $\nu_2(n-1)<n-1$. The equality $\nu_2(c_n)=\nu_2(n-1)$ is thus equivalent to $A$ being even. Denote $n-2=s$ (so $s$ is odd) and $m-2=j$, we get $$ A=\sum_{j=0}^{s-2} {s\choose j}\cdot \frac{(j+2)^{s-j-1}-1}{j+1}. $$ Modulo 2 we have $$\frac{(j+2)^{s-j-1}-1}{j+1}=1+(j+2)+\ldots+(j+2)^{s-j-2}\equiv 1+(j+2)(s-j-2)\equiv 1,$$ so $$ A\equiv \sum_{j=0}^{s-2} {s\choose j}=2^{s-2}-s-1 $$ is even.

Yes. Consider two cases.

  1. Assume that $n$ is even. Then $$c_n=1+\sum_{m=1}^{n-1}m{n\choose m}m^{n-1-m}=c_n=1+\sum_{m=1}^{n-1}n{n-1\choose m-1}m^{n-1-m}$$ is indeed odd.

  2. Let $n>1$ be odd. Then $$c_n=1+n\sum_{m=1}^{n-1}{n-1\choose m-1}+n\sum_{m=2}^{n-2}{n-1\choose m-1}(m^{n-1-m}-1)\\=1+n(2^{n-1}-1)+n(n-1)\sum_{m=2}^{n-2}{n-2\choose m-2}\cdot \frac{m^{n-1-m}-1}{m-1}\\=:1+n(2^{n-1}-1)+n(n-1)A.$$ It already follows that $\nu_2(c_n)\geqslant \nu_2(n-1)$, since $c_n\equiv n\cdot 2^{n-1} \pmod {n-1}$, and $\nu_2(n-1)<n-1$. The equality $\nu_2(c_n)=\nu_2(n-1)$ is thus equivalent to $A$ being even. Modulo 2 we have $$\frac{m^{n-1-m}-1}{m-1}=1+m+\ldots+m^{n-m-2}\equiv 1+m(n-m-2)\equiv 1,$$ so $$ A\equiv \sum_{m=2}^{n-2} {n-2\choose m-2}=2^{n-2}-1-(n-2) $$ is indeed even.

Source Link
Fedor Petrov
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 460