数列の問題

方針 $f(k)$ の値が等しい $k$ をまとめて和を計算する。

$f(k)=m$ となるのは $2^m\leqq k\leqq 2^{m+1}-1$ のときである。$1\leqq k\leqq 2^n-1$ の範囲では $m=0,1,\dots ,n-1$ であり、最後の $k=2^n$ では $f(2^n)=n$ である。よって
$$S_n=\sum _{m=0}^{n-1}m\sum _{k=2^m}^{2^{m+1}-1}k+n\cdot 2^n.$$

内側の和 $k=2^m,\dots ,2^{m+1}-1$ は項数 $2^m$ の等差数列なので
$$\sum _{k=2^m}^{2^{m+1}-1}k=\frac{2^m\{2^m+(2^{m+1}-1)\}}{2}=\frac{3\cdot 4^m-2^m}{2}.$$
したがって
$$S_n=\frac{3}{2}\sum _{m=0}^{n-1}m\cdot 4^m-\frac{1}{2}\sum _{m=0}^{n-1}m\cdot 2^m+n\cdot 2^n.$$

$T={\sum }_{m=0}^{n-1}m\cdot 4^m$ の計算
$T=1\cdot 4+2\cdot 4^2+\cdots +(n-1)4^{n-1}$
$4T=1\cdot 4^2+\cdots +(n-2)4^{n-1}+(n-1)4^n$
辺々引くと
$$-3T=4+4^2+\cdots +4^{n-1}-(n-1)4^n=\frac{4^n-4}{3}-(n-1)4^n.$$
よって $9T=-(4^n-4)+3(n-1)4^n=(3n-4)4^n+4$ より
$$T=\frac{(3n-4)4^n+4}{9}.$$
($n=1$ のとき $T=0$ となり、成り立つ。)

$U={\sum }_{m=0}^{n-1}m\cdot 2^m$ の計算 同様に $U-2U=2+2^2+\cdots +2^{n-1}-(n-1)2^n=2^n-2-(n-1)2^n$ より
$$U=(n-2)2^n+2.$$

まとめ
$$S_n=\frac{3}{2}\cdot \frac{(3n-4)4^n+4}{9}-\frac{(n-2)2^n+2}{2}+n\cdot 2^n$$
$$=\frac{(3n-4)4^n}{6}+\frac{2}{3}-(n-2)2^{n-1}-1+n\cdot 2^n.$$
ここで $-(n-2)2^{n-1}+n\cdot 2^n=2^{n-1}(-n+2+2n)=(n+2)2^{n-1}$、また $\frac{(3n-4)4^n}{6}=\frac{(3n-4)2^{2n-1}}{3}$、$\frac{2}{3}-1=-\frac{1}{3}$ だから
$$S_n=\frac{(3n-4)\cdot 2^{2n-1}+3(n+2)\cdot 2^{n-1}-1}{3}.$$

検算 $n=1$: 直接計算すると $1\cdot 0+2\cdot 1=2$、式は $\frac{(-1)\cdot 2+3\cdot 3\cdot 1-1}{3}=\frac{-2+9-1}{3}=2$。$n=2$: 直接計算すると $0+2+3+4\cdot 2=13$、式は $\frac{2\cdot 8+3\cdot 4\cdot 2-1}{3}=\frac{16+24-1}{3}=13$。$n=3$: 直接計算すると $0+2+3+2(4+5+6+7)+8\cdot 3=73$、式は $\frac{5\cdot 32+3\cdot 5\cdot 4-1}{3}=\frac{160+60-1}{3}=73$。いずれも一致する。

$k=2^n$ のとき $f(k)=n$、$1\le k\le 2^n-1$ では $2^m\le k<2^{m+1}$ ($m=0,\dots ,n-1$) のとき $f(k)=m$ である。

$m$ を固定すると、$k=2^m,\dots ,2^{m+1}-1$ の和は項数 $2^m$、平均 $\frac{3\cdot 2^m-1}{2}$ より $\frac{3\cdot 4^m-2^m}{2}$。よって
$$S_n=n{2}^n+\frac{1}{2}\sum _{m=0}^{n-1}m(3\cdot 4^m-2^m).$$

等比×等差の和の公式より
${\sum }_{m=0}^{n-1}m{2}^m=(n-2)2^n+2$、
${\sum }_{m=0}^{n-1}m{4}^m=\frac{(3n-4)4^n+4}{9}$。

これを代入すると
$$S_n=n{2}^n+\frac{1}{2}\left[\frac{(3n-4)4^n+4}{3}-(n-2)2^n-2\right]=\frac{(3n-4)4^n}{6}+(n+2)2^{n-1}-\frac{1}{3}.$$

検算：$n=1$ のとき $S_1=1\cdot 0+2\cdot 1=2$。公式では $-\frac{2}{3}+3-\frac{1}{3}=2$。$n=2$ のとき $S_2=0+2+3+4\cdot 2=13$。公式では $\frac{32}{6}+8-\frac{1}{3}=13$。いずれも一致する。