2014 dxdy logo

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

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



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


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 А вы можете доказать тождество Лагранжа ММИ
Сообщение26.01.2015, 09:33 


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

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

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

 Профиль  
                  
 
 Re: А вы можете доказать тождество Лагранжа ММИ
Сообщение26.01.2015, 20:43 
Заслуженный участник
Аватара пользователя


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

-- 26.01.2015, 21:12 --

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

 Профиль  
                  
 
 Re: А вы можете доказать тождество Лагранжа ММИ
Сообщение26.01.2015, 21:52 


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

 Профиль  
                  
 
 Re: А вы можете доказать тождество Лагранжа ММИ
Сообщение26.01.2015, 22:01 
Заслуженный участник
Аватара пользователя


27/04/09
21292
Уфа

(Оффтоп)

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

 Профиль  
                  
 
 Re: А вы можете доказать тождество Лагранжа ММИ
Сообщение26.01.2015, 22:04 
Заслуженный участник
Аватара пользователя


24/02/12
1730
Москва
Ну так я написал, как можно устроить "чистую" индукцию. Доказывать вот такое:
$$
\sum_{k=l}^nC_n^kC_n^{k-l}=C_{2n}^{n+l},\quad l=0,\dots,n
$$
индукцией по $n$.

 Профиль  
                  
 
 Re: А вы можете доказать тождество Лагранжа ММИ
Сообщение26.01.2015, 22:49 


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

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

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


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

 Профиль  
                  
 
 Re: А вы можете доказать тождество Лагранжа ММИ
Сообщение27.01.2015, 17:36 
Заслуженный участник
Аватара пользователя


24/02/12
1730
Москва
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*}

 Профиль  
                  
 
 Re: А вы можете доказать тождество Лагранжа ММИ
Сообщение28.01.2015, 15:12 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: А вы можете доказать тождество Лагранжа ММИ
Сообщение28.01.2015, 15:19 
Заморожен


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

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

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



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

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


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

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