binomial Sum.

[man111]

Prove that $\binom{n}{0}\binom{n}{0}-\binom{n+1}{1}\binom{n}{1}+\binom{n+2}{2}\binom{n}{2}............................ = (-1)^n$

[sup]

Все это есть у Д. Кнута, а именно следующее тождество
$\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$

[Simba]

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

[ewert]

Simba в сообщении #401446 писал(а):

$\binom{k}{n}=C^k_n$, ведь так?

Наоборот.

[caxap]

Simba в сообщении #401446 писал(а):

А разве не должно быть условия $k\leqslant n$?

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

[man111]

Thanks to all for nice discussion....

is There is any other Method Means Proof without Induction.

[EtCetera]

Доказательство без использования метода математической индукции:

$$\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!$$

[caxap]

$$\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$.

[sup]

Думаю, можно еще проще, дважды применяя формулу разложения $\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$

[caxap]

(EtCetera)

EtCetera
Супер! Я опять пытался применить ваш коронный подход, но опять ничего не получилось
Видать, надо больше практики. Вы случайно не знаете какой-нибудь учебник/статью, где бы описывались подобные примеры и решение их с помощью производных?

(Странно. Такой мощный метод, а в Конкретной Математике даже не упоминается и нет примеров. А запомнить все тождества оттуда нереально.)

[man111]

Special Thanks to all for giving a Nice Solution.

Thanks.....

[EtCetera]

(сахар)

Увы, я бы и сам не без интереса полистал такую книжку, но... нет, не знаю.
На самом деле, при решении таких задач я пользуюсь только двумя тождествами:
$\dfrac{n!}{(n-m)!}=\left.\left(x^n\right)^{(m)}\right|_{x=1},\ 0\le m\le n$
$n^m=\left.\left(e^{nx}\right)^{(m)}\right|_{x=0},\ m\ge 0$
И каждый раз пытаюсь разглядеть левые части этих тождеств под знаком $\Sigma$...

[caxap]

(EtCetera)

Ясно. Спасибо.