2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Доказательство тождества с биноном
Сообщение31.10.2020, 17:37 
Аватара пользователя


22/11/13
550
Какие существуют элементарные доказательства приведенного ниже тождества?
$$\sum\limits_{k=0}^{n}\binom{n+k}{k}\frac{1}{2^k}=2^n$$
Одно из не элементарных использует тождество
$$\sum\limits_{k=0}^{n}\binom{k+m}{m}z^k=\frac{1}{(1-z)^{m+1}}-\frac{z^{n+1}}{(1-z)^{m+1}}\sum\limits_{k=0}^{m}\binom{n+k}{k}(1-z)^k$$
куда мы подставляем $n=m$ и $z=\frac{1}{2}$
$$\sum\limits_{k=0}^{n}\binom{k+n}{n}\frac{1}{2^k}=\frac{1}{\frac{1}{2^{n+1}}}-\frac{\frac{1}{2^{n+1}}}{\frac{1}{2^{n+1}}}\sum\limits_{k=0}^{n}\binom{n+k}{k}\frac{1}{2^k}$$$$S=2^{n+1}-S, 2S = 2^{n+1}, S=2^n$$

 Профиль  
                  
 
 Re: Доказательство тождества с биноном
Сообщение31.10.2020, 17:46 
Заслуженный участник


20/12/10
9179
kthxbye в сообщении #1490113 писал(а):
Какие существуют элементарные доказательства приведенного ниже тождества?
А индукция по $n$ не годится?

Upd. Годится, но не совсем. Напишем тождество $C_{n+1+k}^k=C_{n+k}^k+C_{n+k}^{k-1}$, разделим его обе части на $2^k$ и просуммируем по $k$ от $0$ до $n+1$. В результате возникнет рекуррентное соотношение $f(n+1)=2f(n)$, где $f(n)$ --- сумма, которую хочется вычислить.

 Профиль  
                  
 
 Re: Доказательство тождества с биноном
Сообщение31.10.2020, 20:00 
Заслуженный участник
Аватара пользователя


27/05/11
878
Есть простое комбинаторное доказательство этого тождества, предложенное Тамасом Лендьелом в 1993 г. (См. здесь, стр. 1).

 Профиль  
                  
 
 Re: Доказательство тождества с биноном
Сообщение06.12.2020, 21:22 


29/06/20
10
Наверное, можно через перемножение производящих функций.
Если, конечно, это достаточно элементарно :wink:

 Профиль  
                  
 
 Re: Доказательство тождества с биноном
Сообщение07.12.2020, 02:11 


21/05/16
4292
Аделаида
Формула (5.20) в Конкретной математике, доказательство буквально в две строчки.

 Профиль  
                  
 
 Re: Доказательство тождества с биноном
Сообщение07.12.2020, 09:16 
Заслуженный участник


20/12/10
9179
kotenok gav в сообщении #1495553 писал(а):
доказательство буквально в две строчки
Ну конечно, две строчки. Сначала нужно придумать тождество (5.19) с многочленами от двух переменных $x$ и $y$ (вот это самое нетривиальное), потом доказать его (одно из доказательств, кстати, по индукции) и, наконец, рассмотреть частный случай $x=y=1$.

 Профиль  
                  
 
 Re: Доказательство тождества с биноном
Сообщение07.12.2020, 10:56 
Заслуженный участник
Аватара пользователя


23/08/07
5502
Нов-ск
То есть доказать
$$\sum\limits_{k=0}^{n}2^{n-k}C_{n+k}^{n}=2^{2n}$$
Слева стоит коэффициент при $x^n$ в полиноме
$$\dfrac{2^{2n+1}-(1+x)^{2n+1}}{1-x}$$
Почленно
$$2^{2n+1}-\sum\limits_{k=0}^{n}C_{2n+1}^k=2^{2n+1}-2^{2n}$$

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

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



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

Сейчас этот форум просматривают: YandexBot [bot]


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

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