А вы можете доказать тождество Лагранжа ММИ

[notabene]

Очень простая задачка. Доказать методом математической индукции тождество Лагранжа
$\binom{n}{0}^2+ \binom{n}{1}^2+ ... + \binom{n}{n}^2 = \binom{2n}{n}

Говорю сразу, решение другим способом, например, комбинаторными рассуждениями про выбор делегации в которой $n$ человек, из коллектива, в котором $n$ мужчин и $n$ женщин я знаю.

Но вот ММИ не получается, есть там одна хитрость. (Или мне так кажется).

[ex-math]

А просто рассмотреть $(1+x)^n(1+x^{-1})^n$ не подойдет?
В индукции там вылезает сумма $C_n^kC_n^{k-1}$.

-- 26.01.2015, 21:12 --

В принципе можно вести индукцию сразу для всех сумм $C_n^kC_n^{k-l}$, но это громоздко и уродливо.

[notabene]

Тут вот в чем закавыка, мы привлекли к доказательству "внешние" средства - фактически воспользовались теорией производящих функций, а интересует "прямое" доказательство.

[arseniiv]

(Оффтоп)

Производящие функции или

notabene в сообщении #968480 писал(а):

комбинаторными рассуждениями

— куда уж прямее? А у доказательств по индукции есть одна особенность: надо уже знать, какую формулу доказывать, тогда как первыми двумя способами её можно сразу и получить.

[ex-math]

Ну так я написал, как можно устроить "чистую" индукцию. Доказывать вот такое:

$$ \sum_{k=l}^nC_n^kC_n^{k-l}=C_{2n}^{n+l},\quad l=0,\dots,n $$

индукцией по $n$.

[notabene]

Докажите. Конкретные вычисления приведите, а не общие рассуждения.

-- Пн янв 26, 2015 23:58:16 --

Цитата:

А у доказательств по индукции есть одна особенность: надо уже знать, какую формулу доказывать, тогда как первыми двумя способами её можно сразу и получить.

Спасибо, кэп!

[ex-math]

ex-math в сообщении #968870 писал(а):

$$ \sum_{k=l}^nC_n^kC_n^{k-l}=C_{2n}^{n+l},\quad l=0,\dots,n $$

Проверяем базу при $n=1,2$ (чтоб уж наверняка). Теперь, предполагая соотношения выше доказанными, докажем аналогичные с заменой $n$ на $n+1$. Для $l=n+1$ очевидно. Для $l=n$ проверяется непосредственно. Пусть теперь $1\leqslant l\leqslant n-1$. Имеем
\begin{multline*} S_{n+1}(l)=\sum_{k=l}^{n+1}C_{n+1}^kC_{n+1}^{k-l}=C_{n+1}^l+\sum_{k=l+1}^n(C_n^k+C_n^{k-1})(C_n^{k-l}+C_n^{k-l-1})+C_{n+1}^{n-l+1}=\\ =C_{n+1}^l+\sum_{k=l+1}^n(C_n^kC_n^{k-l}+C_n^{k-1}C_n^{k-l}+C_n^kC_n^{k-l-1}+C_n^{k-1}C_n^{k-l-1})+C_{n+1}^{n-l+1}=\\ =\vphantom{\sum_{k=l+1}^n}C_n^l+C_n^{l-1}+S_n(l)-C_n^l+S_n(l-1)-C_n^{n-l+1}-C_n^{l-1}+S_n(l+1)+S_n(l)-C_n^{n-l}+C_n^{n-l+1}+C_n^{n-l}=\\ =\vphantom{\sum_{k=l+1}^n}S_n(l-1)+2S_n(l)+S_n(l+1)=C_{2n}^{n+l-1}+C_{2n}^{n+l}+C_{2n}^{n+l}+C_{2n}^{n+l+1}=C_{2n+1}^{n+l}+C_{2n+1}^{n+l+1}=C_{2(n+1)}^{(n+1)+l} \end{multline*}
что и требовалось. Пусть, наконец, $l=0$:
\begin{multline*} S_{n+1}(0)=\sum_{k=0}^{n+1}(C_{n+1}^k)^2=2+\sum_{k=1}^n(C_n^k+C_n^{k-1})^2=2+\sum_{k=1}^n((C_n^k)^2+2C_n^{k}C_n^{k-1}+(C_n^{k-1})^2)=\\ =\vphantom{\sum_{k=l+1}^n}2S_n(0)+2S_n(1)=2C_{2n}^n+2C_{2n}^{n+1}=2C_{2n+1}^{n+1}=C_{2(n+1)}^{n+1}. \end{multline*}

[ex-math]

notabene
Так что? Не понравилось доказательство?
Насчет громоздкости и уродливости честно предупредил.
Как видите, никакой хитрости тут нет.

[nnosipov]

Видимо, здесь типичная для метода индукции штука случилась: возможные проблемы исчезают, стоит только правильно обобщить (усилить) доказываемое утверждение.