2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 binomial Sum.
Сообщение15.01.2011, 18:19 


30/11/10
227
Prove that $\binom{n}{0}\binom{n}{0}-\binom{n+1}{1}\binom{n}{1}+\binom{n+2}{2}\binom{n}{2}............................ = (-1)^n$

 Профиль  
                  
 
 Re: binomial Sum.
Сообщение16.01.2011, 12:16 
Заслуженный участник


22/11/10
1187
Все это есть у Д. Кнута, а именно следующее тождество
$\sum \limits_k \binom{r}{k}\binom{s+k}{n}(-1)^k = (-1)^r \binom{s}{n-r}$
Это тождество доказывается индукцией по $r$.
Случай $r=0$ очевиден. Пусть при $r \leqslant r_0$ все хорошо. Положим $r = r_0 +1$. Тогда $\binom{r_0+1}{k} = \binom{r_0}{k} + \binom{r_0}{k-1}$. По индукционному предположению получим
$\sum \limits_k \binom{r}{k}\binom{s+k}{n}(-1)^k = (-1)^{r_0} \binom{s}{n-r_0} - (-1)^{r_0} \binom{s+1}{n-r_0}= (-1)^r \binom{s}{n-r}$
Отсюда уже легко получаем
$\sum \limits_k \binom{n}{k}\binom{n+k}{k}(-1)^k = \sum \limits_k \binom{n}{k}\binom{n+k}{n}(-1)^k = (-1)^n$

 Профиль  
                  
 
 Re: binomial Sum.
Сообщение18.01.2011, 13:46 


03/10/10
102
Казахстан
$\binom{k}{n}=C^k_n$, ведь так? А разве не должно быть условия $k\leqslant n$?

 Профиль  
                  
 
 Re: binomial Sum.
Сообщение18.01.2011, 13:54 
Заслуженный участник


11/05/08
32166
Simba в сообщении #401446 писал(а):
$\binom{k}{n}=C^k_n$, ведь так?

Наоборот.

 Профиль  
                  
 
 Re: binomial Sum.
Сообщение18.01.2011, 17:11 
Заслуженный участник
Аватара пользователя


07/01/10
2015
Simba в сообщении #401446 писал(а):
А разве не должно быть условия $k\leqslant n$?

$\binom nk=0$ при $k>n$ или $k<0$.

 Профиль  
                  
 
 Re: binomial Sum.
Сообщение18.01.2011, 18:58 


30/11/10
227
Thanks to all for nice discussion....

is There is any other Method Means Proof without Induction.

 Профиль  
                  
 
 Re: binomial Sum.
Сообщение18.01.2011, 20:29 
Заслуженный участник


28/04/09
1933
Доказательство без использования метода математической индукции:
$$\sum\limits_{k=0}^n (-1)^k\binom{n}{k}\binom{n+k}{k}=\sum\limits_{k=0}^n (-1)^k\binom{n}{k}\frac{\left.\left(x^{n+k}\right)^{(n)}\right|_{x=1}}{n!}=\frac{1}{n!}\left.\left(x^n\sum\limits_{k=0}^n\binom{n}{k}(-x)^k\right)^{(n)}\right|_{x=1}=(-1)^n\cdot \frac{\left.\left(x^n(x-1)^n\right)^{(n)}\right|_{x=1}}{n!}$$
По формуле Лейбница получаем:
$$\left.\left(x^n(x-1)^n\right)^{(n)}\right|_{x=1}=\sum\limits_{k=0}^n\binom{n}{k}\left.\left(x^n\right)^{(n-k)}\right|_{x=1}\cdot \left.\left((x-1)^n\right)^{(k)}\right|_{x=1}$$
Но$$\left.\left((x-1)^n\right)^{(k)}\right|_{x=1}=\left\{\begin{array}{ll}0, & 0\le k<n\\ n!, & k=n\end{array}\right.$$
Поэтому
$$\sum\limits_{k=0}^n\binom{n}{k}\left.\left(x^n\right)^{(n-k)}\right|_{x=1}\cdot \left.\left((x-1)^n\right)^{(k)}\right|_{x=1}=\binom{n}{n}\left.\left(x^n\right)^{(0)}\right|_{x=1}\cdot \left.\left((x-1)^n\right)^{(n)}\right|_{x=1}=n!$$

 Профиль  
                  
 
 Re: binomial Sum.
Сообщение18.01.2011, 20:47 
Заслуженный участник
Аватара пользователя


07/01/10
2015
$$\begin{gathered}
\sum_k \binom nk\binom{n+k}k (-1)^k\overset 1=\sum_k \binom nk\binom{n+k}n (-1)^k\overset 2=
\sum_k \binom {n+k}k\binom n{n-k} (-1)^k\overset 3=\\
\overset 3=\sum_k \binom {-n-1}k\binom n{n-k}\overset 4=\binom{-1}n\overset 5=(-1)^n\end{gathered}$$

Все тождества из "Конкретной Математики":
1) Симметрия: $\binom nk=\binom n{n-k}$.
2) $\binom rm\binom mk=\frac{r!}{k!(m-k)!(r-m)!}\cdot \frac{(r-k)!}{(r-k)!}=\binom rk\binom {r-k}{m-k}$.
3) Верхнее обращение: $\binom rk=r^{\underline k}/k!$, $r^{\underline k}=r(r-1)\cdots(r-k+1)=(-1)^k (-r)(1-r)\cdots (k-1-r)=(-1)^k (k-r-1)^{\underline k}$.
4) Свёртка Вандермонда: $(1+z)^r=\sum_k\binom rk z^k$, $(1+z)^s=\sum_k\binom sk z^k$, $[z^n](1+z)^r (1+z)^s=[z^n](1+z)^{r+s}$, $\sum_k \binom rk\binom s{n-k}=\binom{r+s}n$.
5) $\binom{-1}k=(-1)^{\underline{k}}/k!=(-1)^k$.

 Профиль  
                  
 
 Re: binomial Sum.
Сообщение18.01.2011, 22:13 
Заслуженный участник


22/11/10
1187
Думаю, можно еще проще, дважды применяя формулу разложения $\binom{a}{b} = \binom{a-1}{b} +\binom{a-1}{b-1}$.
$S(r,n)=\sum \limits_k \binom{r}{k}\binom{n+k}{r}(-1)^k = \sum \limits_k (\binom{r-1}{k} +\binom{r-1}{k-1})\binom{n+k}{r}(-1)^k =$
$\sum \limits_k \binom{r-1}{k}\binom{n+k}{r}(-1)^k - \sum \limits_k \binom{r-1}{k} \binom{n+k+1}{r}(-1)^k =$
$ -\sum \limits_k \binom{r-1}{k}\binom{n+k}{r-1}(-1)^k = -S(r-1,n)$
$S(r,n)=-S(r-1,n)=S(r-2,n)= ... (-1)^r$

 Профиль  
                  
 
 Re: binomial Sum.
Сообщение18.01.2011, 22:13 
Заслуженный участник
Аватара пользователя


07/01/10
2015

(EtCetera)


 Профиль  
                  
 
 Re: binomial Sum.
Сообщение20.01.2011, 15:08 


30/11/10
227
Special Thanks to all for giving a Nice Solution.

Thanks.....

 Профиль  
                  
 
 Re: binomial Sum.
Сообщение20.01.2011, 20:10 
Заслуженный участник


28/04/09
1933

(сахар)


 Профиль  
                  
 
 Re: binomial Sum.
Сообщение20.01.2011, 20:52 
Заслуженный участник
Аватара пользователя


07/01/10
2015

(EtCetera)


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

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



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

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


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

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