Sumy oparte na funkcji podłoga

[irtomek]

Dzień dobry, mam ogromny problem z obliczeniem danych sum:

\(\displaystyle{ S_n = \sum_{k \ge 1} \left\lfloor \frac{n}{2^k} + \frac{1}{2} \right\rfloor}\)
oraz
\(\displaystyle{ T_n = \sum_{k \ge 1} 2^k \left\lfloor \frac{n}{2^k} + \frac{1}{2} \right\rfloor ^2}\)

Próbowałem porównywać kolejno wyrazy i zawsze dochodziłem do słabych wniosków, niewystarczająco pewnych.

[Adifek]

Podpowiem, że \(\displaystyle{ \left\lfloor \frac{n}{2^k} + \frac{1}{2} \right\rfloor = 0}\) gdy \(\displaystyle{ \frac{n}{2^k} + \frac{1}{2} <1}\), a więc gdy \(\displaystyle{ k> \log_{2}2n}\). Stąd:

\(\displaystyle{ S_n = \sum_{k \ge 1} \left\lfloor \frac{n}{2^k} + \frac{1}{2} \right\rfloor = \sum_{ 1\le k\le \log_{2}(2n) } \left\lfloor \frac{n}{2^k} + \frac{1}{2} \right\rfloor}\)

[irtomek]

Widzę, że porwałem się z motyką na Słońce. Mam tragiczne problemy w obliczeniu tej sumy. W ogóle nie mam pojęcia skąd autorzy książek biorą "genialne" pomysły na obliczanie konkretnych sum.-- 16 sie 2013, o 21:17 --Moje rozważania to:
\(\displaystyle{ \sum_{1 \le k \le \log_{2} (2n)} \lfloor \frac{n}{2^k} +
\frac{1}{2} \rfloor = \sum_{1 \le k \le \log_{2} (2n)} \sum_{j} [ 1 \le j \le \frac{n}{2^k} +\frac{1}{2} ] = \\
\sum_{j\ge1,k} [1 \le k \le \log_{2} \frac{n}{j - \frac{1}{2}} ] = \sum_{j} \lfloor \log_{2} \frac{n}{j - \frac{1}{2}} \rfloor}\)

W ostatnim wierszu łatwo wyliczyć zakres j, jednak dalej wydaje mi się, że zatoczyłem koło ...