сумма, зависящая от двоичной записи индекса

[maxal]

Пусть $n$ - натуральное число. Доказать, что

$$\sum_{i=1}^{2^n-1} e_i\cdot i^n = (-1)^n 2^{n^2-1},$$

где $e_i=0,$ если $i$ в двоичной записи оканчивается на нечетное число нулей;
в противном же случае $e_i=(-1)^{\mbox{\footnotesize количество единиц в двоичной записи}\ i}.$

Пример для $n=2:$

$$-1\cdot 1^2 + 0\cdot 2^2 + 1\cdot 3^2 = 2^{2^2-1} = 8$$

[RIP]

Обозначим

$$S_{n,m}=\sum_{k=1}^{2^n-1}e_kk^m.$$

Учитывая

$$e_{2^n-k}=(-1)^{n-1}e_k,$$

легко по индукции получить

$$S_{n,0}=\begin{cases}-1,&\text{n - нечет;}\\ 0,&\text{n - чет;} \end{cases}$$

$$S_{n,m}=(-1)^n2^{mn-1},\ 1\leqslant m\leqslant n.$$

В частности,

$$S_{n,n}=\sum_{k=1}^{2^n-1}e_kk^n=(-1)^n2^{n^2-1}.$$

[Руст]

Непонятно, как производится шаг индукции.

[RIP]

Я имел в виду нечто вроде

$$S_{n,m}=e_{2^{n-1}}2^{m(n-1)}+S_{n-1,m}+(-1)^{n-1}\sum_{l=0}^m\binom ml2^{n(m-l)}(-1)^lS_{n-1,l}$$

Не хотел писать полное решение, чтоб оставалось над чем подумать тем, кто хочет решить задачу самостоятельно.