AMM Problem
AMM Problem 11544
Max Alekseyev,
Department of Computer Science and Engineering, University of South Carolina.
Frank Ruskey, Department of Computer Science, University of Victoria.
$\def\I#1{{[\![#1]\!]}} % Iversonian$
Our solution to the problem:
We make two observations initially.
First, for any function $A(m)$,
if $A(0) = 0$ then $A(m) = \sum_{1 \le n \le m} \left( A(n) - A(n-1) \right)$
because all terms cancel each other except $A(m)$.
Secondly, if $t (2k+1) = n+k$, then multiplying by 2 and subtracting $2k+1$ we obtain the middle equation below:
\[
(2t-1)(2k+1) = 2t(2k+1) - (2k+1) = 2(n+k) -(2k+1) = 2n-1.
\]
Thus, since any divisor of an odd number must be odd,
\[
\I{ 2k+1 \ \backslash \ n+k } = \I{ 2k+1 \ \backslash \ 2n-1 },
\]
where $\I{P}$ is $0$ or $1$ depending on whether $P$ is true or not and
$\backslash$ is the "divides" symbol popularized in the book
Concrete
Mathematics as an alternative to $|$.
We can now proceed as follows, where $A(m)$ is the sum that we are
trying to evaluate:
\begin{align*}
A(m)
& = \sum_{k=0}^{m-1} \phi(2k+1) \left\lfloor \frac{m+k}{2k+1} \right\rfloor \\
& = \sum_{n=1}^m \left( A(n) - A(n-1) \right) \ \ \ \ \ \text{Note that $A(0)=0$.} \\
& = \sum_{n=1}^m \left( \sum_{k=0}^{n-1} \phi(2k+1) \left\lfloor \frac{n+k}{2k+1} \right\rfloor
- \sum_{k=0}^{n-2} \phi(2k+1) \left\lfloor \frac{n-1+k}{2k+1} \right\rfloor \right) \\
& = \sum_{n=1}^m \sum_{k=0}^{n-1} \phi(2k+1) \left( \left\lfloor \frac{n+k}{2k+1} \right\rfloor
- \left\lfloor \frac{n+k-1}{2k+1} \right\rfloor \right) \\
& = \sum_{n=1}^m \sum_{k=0}^{n-1} \phi(2k+1) \I{ 2k+1 \ \backslash \ n+k } \\
& = \sum_{n=1}^m \sum_{k=0}^{n-1} \phi(2k+1) \I{ 2k+1 \ \backslash \ 2n-1 } \\
& = \sum_{n=1}^m \sum_{2k+1 \backslash 2n-1} \phi(2k+1) \\
& = \sum_{n=1}^m (2n-1) \\
& = m^2.
\end{align*}