2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 сумма, зависящая от двоичной записи индекса
Сообщение10.12.2006, 12:46 
Модератор
Аватара пользователя


11/01/06
5660
Пусть $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$$

 Профиль  
                  
 
 
Сообщение10.12.2006, 20:28 
Заслуженный участник
Аватара пользователя


11/01/06
3822
Обозначим
$$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}.$$

 Профиль  
                  
 
 
Сообщение10.12.2006, 21:29 
Заслуженный участник


09/02/06
4382
Москва
Непонятно, как производится шаг индукции.

 Профиль  
                  
 
 
Сообщение10.12.2006, 21:45 
Заслуженный участник
Аватара пользователя


11/01/06
3822
Я имел в виду нечто вроде
$$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}$$
Не хотел писать полное решение, чтоб оставалось над чем подумать тем, кто хочет решить задачу самостоятельно.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group