Return to Answer

Actually both (2) and (3) are true, and there is a very short proof:

First of all we have that $$s_n=\sum_{d|n+1, d< n+1}d\sum_{i=1, (i, (n+1)/d)=1}^{(n+1)/d-1}(-1)^{id-1}.$$

Sorry for the bad typesetting, the compiler here doesn't seem to like \substack. Ok to be sure this is clear, the inner sum is over $i$ running from $1$ to $(n+1)/d-1,$ which are coprime to $(n+1)/d$.

First notice for later reference that when $d$ is even the inner sum over $i$ is negative. On the other hand if $d$ is odd then the inner sum is equal to $$\sum_{i=1, (i, (n+1)/d)=1}^{(n+1)/d-1}(-1)^{i-1}.$$ Furthermore if $(n+1)/d$ is odd then the map $i\mapsto (n+1)/d-i$ is a bijection between integers coprime to $(n+1)/d$, and it reverses parity. Therefore when both $d$ and $(n+1)/d$ are odd we have that $$\sum_{i=1, (i, (n+1)/d)=1}^{(n+1)/d-1}(-1)^{i-1}=0.$$ Plugging this in above proves (3) right away.

To prove (2) we write $n+1=2^km$ with $m$ odd. Suppose that $d|(n+1),~d<(n+1)/2,$ and $d$ is odd. Then $2^k d|(n+1)$ and $2^k d < n+1,$ and pairing the contribution in the above sum from $d$ with that from $2^kd$ gives $$d\sum_{i=1, (i, (n+1)/d)=1}^{(n+1)/d-1}(-1)^{i-1}-2^kd\sum_{i=1, (i, (n+1)/2^kd)=1}^{(n+1)/2^kd-1}1$$ $$\le d\varphi \left( 2^k\cdot\frac{n+1}{2^kd}\right)-2^kd\varphi \left(\frac{n+1}{2^kd}\right)$$ $$=-2^{k-1}d\varphi \left(\frac{n+1}{2^kd}\right)<0.$$ As we mentioned before, all of the even divisors $d$ contribute a negative amount to $s_n$, so everything is accounted for except for the case when $d=(n+1)/2$ is odd. However this case is easy, the inner sum over $i$ is then $$\sum_{i=1, (i,2)=1}^1(-1)^i=-1<0.$$ So to summarize, the even divisors contribute a negative amount to the overall sum, we pair every odd divisor $d$ with the contribution from $2^kd$ to get a negative quantity, and we deal with $(n+1)/2$ separately if necessary. That finishes the proof.

Actually both (2) and (3) are true, and there is a relatively short proof:

First of all we have that $$s_n=\sum_{d|n+1, d< n+1}d\sum_{i=1, (i, (n+1)/d)=1}^{(n+1)/d-1}(-1)^{id-1}.$$

Sorry for the bad typesetting, the compiler here doesn't seem to like \substack. Ok to be sure this is clear, the inner sum is over $i$ running from $1$ to $(n+1)/d-1,$ which are coprime to $(n+1)/d$.

First notice for later reference that when $d$ is even the inner sum over $i$ is negative. On the other hand if $d$ is odd then the inner sum is equal to $$\sum_{i=1, (i, (n+1)/d)=1}^{(n+1)/d-1}(-1)^{i-1}.$$ Furthermore if $(n+1)/d$ is odd then the map $i\mapsto (n+1)/d-i$ is a bijection between integers coprime to $(n+1)/d$, and it reverses parity. Therefore when both $d$ and $(n+1)/d$ are odd we have that $$\sum_{i=1, (i, (n+1)/d)=1}^{(n+1)/d-1}(-1)^{i-1}=0.$$ Plugging this in above proves (3) right away.

To prove (2) we write $n+1=2^km$ with $m$ odd. Suppose that $d|(n+1),~d<(n+1)/2,$ and $d$ is odd. Then $2^k d|(n+1)$ and $2^k d < n+1,$ and pairing the contribution in the above sum from $d$ with that from $2^kd$ gives $$d\sum_{i=1, (i, (n+1)/d)=1}^{(n+1)/d-1}(-1)^{i-1}-2^kd\sum_{i=1, (i, (n+1)/2^kd)=1}^{(n+1)/2^kd-1}1$$ $$\le d\varphi \left( 2^k\cdot\frac{n+1}{2^kd}\right)-2^kd\varphi \left(\frac{n+1}{2^kd}\right)$$ $$=-2^{k-1}d\varphi \left(\frac{n+1}{2^kd}\right)<0.$$ As we mentioned before, all of the even divisors $d$ contribute a negative amount to $s_n$, so everything is accounted for except for the case when $d=(n+1)/2$ is odd. In this case we have that $k=1$, and the term in the top sum corresponding to $d=(n+1)/2$ is $$ \frac{n+1}{2}\sum_{i=1, (i,2)=1}^1 (-1)^{i-1} = \frac{n+1}{2} . $$

However using our previous calculation the sum of contributions from all of the other odd divisors $e<(n+1)/2$, paired with the divisors $2e$, is $$\le -\sum_{e|(n+1)/2,e<(n+2)/2}e\varphi\left(\frac{n+1}{2e}\right)$$ $$=-\frac{n+1}{2}\cdot\sum_{e|(n+1)/2,e>1}\frac{\varphi (e)}{e}$$ $$=-\frac{n+1}{2}\left(\prod_{p^a||(n+1)/2}\left(1+a(1-1/p)\right)-1\right).$$ Now if $(n+1)/2$ is composite then either $a>1$ for one of the primes above, or there is more than one prime in the product above (also if you are trying to follow this calculation then note that all primes in the product above must be odd). In either case it is trivial to check that the quantity above is strictly less than $-(n+1)/2$, therefore $s_n<0$.

So to summarize, the even divisors contribute a negative amount to the overall sum, we pair every odd divisor $d$ with the contribution from $2^kd$ to get a negative quantity, and we combine these quantities with the divisor $(n+1)/2$ if it is odd. That finishes the proof.

Yes (2) and (3) are both true, here is a proof:

First of all we have that $$s_n=\sum_{d|n+1, d< n+1}d\sum_{i=1, (i, (n+1)/d)=1}^{(n+1)/d-1}(-1)^{id-1}.$$

Sorry for the bad typesetting, the compiler here doesn't seem to like \substack. Ok to be sure this is clear, the inner sum is over $i$ running from $1$ to $(n+1)/d-1,$ which are coprime to $(n+1)/d$.

First notice for later reference that when $d$ is even the inner sum over $i$ is negative. On the other hand if $d$ is odd then the inner sum is equal to $$\sum_{i=1, (i, (n+1)/d)=1}^{(n+1)/d-1}(-1)^{i-1}.$$ Furthermore if $(n+1)/d$ is odd then the map $i\mapsto (n+1)/d-i$ is a bijection between integers coprime to $(n+1)/d$, and it reverses parity. Therefore when both $d$ and $(n+1)/d$ are odd we have that $$\sum_{i=1, (i, (n+1)/d)=1}^{(n+1)/d-1}(-1)^{i-1}=0.$$ Plugging this in above proves (3) right away.

To prove (2) we write $n+1=2^km$ with $m$ odd. Suppose that $d|(n+1),~d<(n+1)/2,$ and $d$ is odd. Then $2^k d|(n+1)$ and $2^k d < n+1,$ and pairing the contribution in the above sum from $d$ with that from $2^kd$ gives $$d\sum_{i=1, (i, (n+1)/d)=1}^{(n+1)/d-1}(-1)^{i-1}-2^kd\sum_{i=1, (i, (n+1)/2^kd)=1}^{(n+1)/2^kd-1}1$$ $$\le d\varphi \left( 2^k\cdot\frac{n+1}{2^kd}\right)-2^kd\varphi \left(\frac{n+1}{2^kd}\right)$$ $$=-2^{k-1}d\varphi \left(\frac{n+1}{2^kd}\right)<0.$$ As we mentioned before, all of the even divisors $d$ contribute a negative amount to $s_n$, so everything is accounted for except for the case when $d=(n+1)/2$ is odd. However this case is easy, the inner sum over $i$ is then $$\sum_{i=1, (i,2)=1}^1(-1)^i=-1<0.$$ So to summarize, the even divisors contribute a negative amount to the overall sum, we pair every odd divisor $d$ with the contribution from $2^kd$ to get a negative quantity, and we deal with $(n+1)/2$ separately if necessary. That finishes the proof.

Actually both (2) and (3) are true, and there is a very short proof:

First of all we have that $$s_n=\sum_{d|n+1, d< n+1}d\sum_{i=1, (i, (n+1)/d)=1}^{(n+1)/d-1}(-1)^{id-1}.$$

Sorry for the bad typesetting, the compiler here doesn't seem to like \substack. Ok to be sure this is clear, the inner sum is over $i$ running from $1$ to $(n+1)/d-1,$ which are coprime to $(n+1)/d$.

First notice for later reference that when $d$ is even the inner sum over $i$ is negative. On the other hand if $d$ is odd then the inner sum is equal to $$\sum_{i=1, (i, (n+1)/d)=1}^{(n+1)/d-1}(-1)^{i-1}.$$ Furthermore if $(n+1)/d$ is odd then the map $i\mapsto (n+1)/d-i$ is a bijection between integers coprime to $(n+1)/d$, and it reverses parity. Therefore when both $d$ and $(n+1)/d$ are odd we have that $$\sum_{i=1, (i, (n+1)/d)=1}^{(n+1)/d-1}(-1)^{i-1}=0.$$ Plugging this in above proves (3) right away.

To prove (2) we write $n+1=2^km$ with $m$ odd. Suppose that $d|(n+1),~d<(n+1)/2,$ and $d$ is odd. Then $2^k d|(n+1)$ and $2^k d < n+1,$ and pairing the contribution in the above sum from $d$ with that from $2^kd$ gives $$d\sum_{i=1, (i, (n+1)/d)=1}^{(n+1)/d-1}(-1)^{i-1}-2^kd\sum_{i=1, (i, (n+1)/2^kd)=1}^{(n+1)/2^kd-1}1$$ $$\le d\varphi \left( 2^k\cdot\frac{n+1}{2^kd}\right)-2^kd\varphi \left(\frac{n+1}{2^kd}\right)$$ $$=-2^{k-1}d\varphi \left(\frac{n+1}{2^kd}\right)<0.$$ As we mentioned before, all of the even divisors $d$ contribute a negative amount to $s_n$, so everything is accounted for except for the case when $d=(n+1)/2$ is odd. However this case is easy, the inner sum over $i$ is then $$\sum_{i=1, (i,2)=1}^1(-1)^i=-1<0.$$ So to summarize, the even divisors contribute a negative amount to the overall sum, we pair every odd divisor $d$ with the contribution from $2^kd$ to get a negative quantity, and we deal with $(n+1)/2$ separately if necessary. That finishes the proof.

Yes (2) and (3) are true, here is a proof:

First of all we have that $$s_n=\sum_{d|n+1, d< n+1}d\sum_{i=1, (i, (n+1)/d)=1}^{(n+1)/d-1}(-1)^{id-1}.$$

Sorry for the bad typesetting, the compiler here doesn't seem to like \substack. Ok to be sure this is clear, the inner sum is over $i$ running from $1$ to $(n+1)/d-1,$ which are coprime to $(n+1)/d$.

First notice for later reference that when $d$ is even the inner sum over $i$ is negative. On the other hand if $d$ is odd then the inner sum is equal to $$\sum_{i=1, (i, (n+1)/d)=1}^{(n+1)/d-1}(-1)^{i-1}.$$ Furthermore if $(n+1)/d$ is odd then the map $i\mapsto (n+1)/d-i$ is a bijection between integers coprime to $(n+1)/d$, and it reverses parity. Therefore when both $d$ and $(n+1)/d$ are odd we have that $$\sum_{i=1, (i, (n+1)/d)=1}^{(n+1)/d-1}(-1)^{i-1}=0.$$ This proves (3) right away, and we will also use it again below.

To prove (2) we write $n+1=2^km$ with $m$ odd. Suppose that $d|(n+1),~d<(n+1)/2,$ and $d$ is odd. Then $2^k d|(n+1)$ and $2^k d < n+1,$ and we have that $$d\sum_{i=1, (i, (n+1)/d)=1}^{(n+1)/d-1}(-1)^{i-1}-2^kd\sum_{i=1, (i, (n+1)/2^kd)=1}^{(n+1)/2^kd-1}1$$ $$\le d\varphi \left( 2^k\cdot\frac{n+1}{2^kd}\right)-2^kd\varphi \left(\frac{n+1}{2^kd}\right)$$ $$=-2^{k-1}d\varphi \left(\frac{n+1}{2^kd}\right)<0.$$ As we mentioned before, all of the even divisors $d$ contribute a negative amount to the sum above, so everything is accounted for except for the case when $d=(n+1)/2$ is odd. However this case is easy, the inner sum over $i$ is then $$\sum_{i=1, (i,2)=1}^2(-1)^i=-1<0.$$ So to summarize, the even divisors contribute a negative amount to the overall sum, we pair every odd divisor $d$ with the contribution from $2^kd$ to get a negative contribution, and we deal with $(n+1)/2$ separately if necessary. That finishes the proof.

Yes (2) and (3) are both true, here is a proof:

First of all we have that $$s_n=\sum_{d|n+1, d< n+1}d\sum_{i=1, (i, (n+1)/d)=1}^{(n+1)/d-1}(-1)^{id-1}.$$

Sorry for the bad typesetting, the compiler here doesn't seem to like \substack. Ok to be sure this is clear, the inner sum is over $i$ running from $1$ to $(n+1)/d-1,$ which are coprime to $(n+1)/d$.

First notice for later reference that when $d$ is even the inner sum over $i$ is negative. On the other hand if $d$ is odd then the inner sum is equal to $$\sum_{i=1, (i, (n+1)/d)=1}^{(n+1)/d-1}(-1)^{i-1}.$$ Furthermore if $(n+1)/d$ is odd then the map $i\mapsto (n+1)/d-i$ is a bijection between integers coprime to $(n+1)/d$, and it reverses parity. Therefore when both $d$ and $(n+1)/d$ are odd we have that $$\sum_{i=1, (i, (n+1)/d)=1}^{(n+1)/d-1}(-1)^{i-1}=0.$$ Plugging this in above proves (3) right away.

To prove (2) we write $n+1=2^km$ with $m$ odd. Suppose that $d|(n+1),~d<(n+1)/2,$ and $d$ is odd. Then $2^k d|(n+1)$ and $2^k d < n+1,$ and pairing the contribution in the above sum from $d$ with that from $2^kd$ gives $$d\sum_{i=1, (i, (n+1)/d)=1}^{(n+1)/d-1}(-1)^{i-1}-2^kd\sum_{i=1, (i, (n+1)/2^kd)=1}^{(n+1)/2^kd-1}1$$ $$\le d\varphi \left( 2^k\cdot\frac{n+1}{2^kd}\right)-2^kd\varphi \left(\frac{n+1}{2^kd}\right)$$ $$=-2^{k-1}d\varphi \left(\frac{n+1}{2^kd}\right)<0.$$ As we mentioned before, all of the even divisors $d$ contribute a negative amount to $s_n$, so everything is accounted for except for the case when $d=(n+1)/2$ is odd. However this case is easy, the inner sum over $i$ is then $$\sum_{i=1, (i,2)=1}^1(-1)^i=-1<0.$$ So to summarize, the even divisors contribute a negative amount to the overall sum, we pair every odd divisor $d$ with the contribution from $2^kd$ to get a negative quantity, and we deal with $(n+1)/2$ separately if necessary. That finishes the proof.