## Task A-4.7.

Let $n$ be a natural number. Each of the numbers $n, n+1, n+2, \ldots, 2 n-1$ has a greatest odd divisor. Determine the sum of these greatest odd divisors.
## Solution.

Let $d(k)$ be the greatest odd divisor of the number $k$.

If $k$ is odd, then $d(k)=k$.

For any $k$, $d(2 k)=d(k)$ holds.

Let $s(n)=d(n)+d(n+1)+\cdots+d(2 n-1)$.

Denote the desired sum by $s(n)=d(2 n-1)+d(2 n-2)+s(n-1)-d(n-1)$

Since $d(2 n-1)=2 n-1$ and $d(2 n-2)=d(n-1)$, we conclude that

$$
s(n)=s(n-1)+2 n-1
$$

It follows that

$$
\begin{aligned}
s(n) & =s(n-1)+2 n-1 \\
& =s(n-2)+(2 n-3)+(2 n-1) \\
& =\cdots \\
& =1+3+\cdots+(2 n-1)
\end{aligned}
$$

Since $1+3+\cdots+(2 n-1)=n^{2}$, the desired sum is $s(n)=n^{2}$.

Note: If it is known that $s(n)=s(n-1)+2 n-1$, then the formula $s(n)=n^{2}$ can be guessed based on small $n$ and proven by mathematical induction. The statement formulation earns 2 points, the base case of induction does not earn points, and the induction step earns 2 points. If the student omits the base case of induction, 1 point should be deducted.