MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

4 Fixed the concluding argument

Actually both (2) and (3) are true, and there is a very 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. However In this case we have that $k=1$, and the term in the top sum corresponding to $d=(n+1)/2$ is easy, $$\frac{n+1}{2}\sum_{i=1, (i,2)=1}^1 (-1)^{i-1} = \frac{n+1}{2} .$$

However using our previous calculation the inner sum over of contributions from all of the other odd divisors $i$ 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 $$\sum_{i=1, a>1 for one of the primes above, or there is more than one prime in the product above (i,2)=1}^1(-1)^i=-1<0.$$ 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 deal combine these quantities with the divisor$(n+1)/2$separately if necessaryit is odd. That finishes the proof. 3 added 21 characters in body Yes Actually both (2) and (3) are both true, here 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. 2 Minor touch-ups and clarification; added 5 characters in body 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.$$ This Plugging this in above 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 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 the sum above,$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}^2(-1)^i=-1i,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 contributionquantity, and we deal with$(n+1)/2\$ separately if necessary. That finishes the proof.

1