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*}