[seqfan] Re: identity

[Max Alekseyev]

On Wed, Feb 3, 2010 at 10:19 PM, Frank Ruskey <ruskey at cs.uvic.ca> wrote:
> Does anyone know why I might find a proof of this or similar
> identities?  n is an even integer.  In maple, so phi = totient
>
> sum( phi(2*k+1)*round((n-1)/(2*(2*k+1))), k = 0..(n/2)-1 ) = n^2/4
>
> The round is just floor((n+2k-2)/(4k+2)) in disguise.  I could
> probably use the fact that floor(a/b)-floor((a-1)/b) = 1 if b|a and
> 0 otherwise, but if it has already been done ...
> Cheers,
> -Frank

First, I guess there is a typo:
round((n-1)/(2*(2*k+1))) equals floor((n+2k)/(4k+2)), not
floor((n+2k-2)/(4k+2)).

Second, plugging n=2m, we get the identity

\sum_{k=0}^{m-1} phi(2*k+1) * floor((m+k)/(2*k+1)) = m^2

Proof.

Let t = floor((m+k)/(2*k+1)) and j = (m+k) mod (2*k+1). Then
t * (2*k+1) = m + k - j
and thus
(2*t-1)(2*k+1) = 2*(m-j) - 1.
In other words, d=(2*k+1) is a divisor of 2*(m-j) - 1 (notice that
both these numbers are odd).
We notice also that t>0 and hence j<m.

Therefore,
\sum_{k=0}^{m-1} phi(2*k+1) * floor((m+k)/(2*k+1))
= \sum_{j=0}^{m-1} \sum_{d | 2*(m-j) - 1} phi(d)
= \sum_{j=0}^{m-1} (2*(m-j) - 1) = m^2
as required.

Regards,
Max