XXXIV OM - II - Zadanie 4

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

Niech $a(k)$ będzie największą liczbą nieparzystą, przez którą dzieli się $k$ . Udowodnić, że

$ \sum_{k=1}^{2^n} a(k) = \frac{1}{3}(4^n+2). $

Rozwiązanie

Największy dzielnik nieparzysty $a(k)$ liczby $k$ możemy otrzymać w następujący sposób. Jeśli $k$ jest liczbą nieparzystą, to $a(k)= k$ , w przeciwnym razie rozważamy liczbę $k/2$ . Jeśli $k/2$ jest liczbą nieparzystą, to $a(k) = k/2$ , w przeciwnym razie rozważamy liczbę $k/4$ itd.

Wobec tego szukaną sumę otrzymamy odejmując od sumy kolejnych liczb naturalnych od $1$ do $2^n$ połówki co drugiego składnika, następnie czwarte części co czwartego składnika, dalej ósme części co ósmego składnika itd. Zatem

$ \begin{split} \sum_{k=1}^{2^n} a(k) &= \sum_{k=1}^{2^n} k - \sum_{k=1}^{2^{n-1}} k - \sum_{k=1}^{2^{n-2}}k - \ldots - \sum_{k=1}^{2} k -1 = \\&= \frac{2^n(2^n+1)}{2} - \frac{2^{n-1}(2^{n-1}+1)}{2} - \frac{2^{n-2}(2^{n-2}+1)}{2} - \ldots - \frac{2(2+1)}{2} -1=\\ &=\frac{1}{2} \cdot 2^n(2^n+1) - \sum_{m=0}^{n-1} \frac{1}{2} \cdot 2^m(2^m+1) =\\ &= \frac{1}{2} (4^n + 2^n) - \frac{1}{2} \sum_{m=0}^{n-1} 4^m - \frac{1}{2} \sum_{m=0}^{n-1} 2^m = \frac{1}{2} (4^n+2^n) - \frac{4^n-1}{4-1} - \frac{2^n-1}{2-1}=\\ &= \frac{1}{2} \left( 4^n+ 2^n - \frac{1}{3} \cdot 4^n + \frac{1}{3} - 2^n + 1 \right) = \frac{1}{3} (4^n+2). \end{split} $