For a positive integer $n$, let $f(n)$ be the number obtained by
writing $n$ in binary and replacing every 0 with 1 and vice
versa. For example, $n=23$ is 10111 in binary, so $f(n)$ is 1000 in
binary, therefore $f(23) =8$. Prove that
\[\sum_{k=1}^n f(k) \leq \frac{n^2}{4}.\]
When does equality hold?

(Proposed by Stephan Wagner, Stellenbosch University)

1. **Understanding the function \( f(n) \)**:
   - For a positive integer \( n \), \( f(n) \) is defined as the number obtained by writing \( n \) in binary and replacing every 0 with 1 and vice versa.
   - For example, if \( n = 23 \), its binary representation is \( 10111 \). Replacing 0 with 1 and vice versa, we get \( 01000 \), which is 8 in decimal. Thus, \( f(23) = 8 \).

2. **Expression for \( f(n) \)**:
   - Note that \( n + f(n) \) is a number consisting entirely of 1s in binary, where the number of 1s is equal to the number of bits in the binary representation of \( n \).
   - If \( n \) has \( t \) bits, then \( n + f(n) = 2^t - 1 \).
   - Therefore, \( f(n) = 2^t - 1 - n \), where \( t = \lfloor \log_2 n \rfloor + 1 \).

3. **Sum of \( f(k) \) from 1 to \( n \)**:
   - We need to prove that \(\sum_{k=1}^n f(k) \leq \frac{n^2}{4}\).
   - Using the expression for \( f(n) \), we have:
     \[
     f(k) = 2^{\lfloor \log_2 k \rfloor + 1} - 1 - k
     \]
   - Therefore, the sum becomes:
     \[
     \sum_{k=1}^n f(k) = \sum_{k=1}^n \left(2^{\lfloor \log_2 k \rfloor + 1} - 1 - k\right)
     \]

4. **Simplifying the sum**:
   - Let \( S = \sum_{k=1}^n 2^{\lfloor \log_2 k \rfloor + 1} \).
   - We need to show that \( S - \sum_{k=1}^n (1 + k) \leq \frac{n^2}{4} \).

5. **Counting the occurrences of \( 2^{\lfloor \log_2 k \rfloor + 1} \)**:
   - The number \( 2^{\lfloor \log_2 k \rfloor + 1} \) appears \( 2^{\lfloor \log_2 k \rfloor} \) times in the sum \( S \), except for the highest power of 2, which appears \( r + 1 \) times, where \( n = 2^t + r \) and \( 0 \leq r < 2^t \).

6. **Calculating \( S \)**:
   - Let \( t = \lfloor \log_2 n \rfloor \). Then:
     \[
     S = \sum_{k=1}^t 2^k \cdot 2^{k-1} + 2^{t+1}(r+1)
     \]
   - Simplifying the first part:
     \[
     \sum_{k=1}^t 2^k \cdot 2^{k-1} = \sum_{k=1}^t 2^{2k-1}
     \]
   - This is a geometric series with the sum:
     \[
     \sum_{k=1}^t 2^{2k-1} = 2 \left( \frac{2^{2t} - 1}{3} \right) = \frac{2^{2t+1} - 2}{3}
     \]
   - Therefore:
     \[
     S = \frac{2^{2t+1} - 2}{3} + 2^{t+1}(r+1)
     \]

7. **Final inequality**:
   - We need to prove:
     \[
     \frac{2^{2t+1} - 2}{3} + 2^{t+1}(r+1) \leq \frac{n^2}{4} + \frac{n(n+1)}{2} + n
     \]
   - Substituting \( n = 2^t + r \):
     \[
     \frac{2^{2t+1} - 2}{3} + 2^{t+1}(r+1) \leq \frac{(2^t + r)^2}{4} + \frac{(2^t + r)(2^t + r + 1)}{2} + (2^t + r)
     \]

8. **Equality condition**:
   - Equality holds if and only if \( 2^{t+1} = 3(2^t - r + 1) \pm 1 \).
   - This implies \( n = 2^{2l+1} + \frac{2^{2l+1} - 2}{3} \) or \( n = 2^{2s} + \frac{2^{2s} - 4}{3} \).

\(\blacksquare\)

The final answer is \( \boxed{ \sum_{k=1}^n f(k) \leq \frac{n^2}{4} } \).