XXXIV OM - II - Zadanie 4

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

\[<br />
\sum_{k=1}^{2^n} a(k) = \frac{1}{3}(4^n+2).<br />
\]

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

\[<br />
\begin{split}<br />
\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 =<br />
\\&= \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=\\<br />
&=\frac{1}{2} \cdot 2^n(2^n+1) - \sum_{m=0}^{n-1} \frac{1}{2} \cdot 2^m(2^m+1) =\\<br />
&= \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}=\\<br />
 &= \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).<br />
\end{split}<br />
\]

Komentarze

Dodaj nową odpowiedź