Комбинаторика сумма сочетаний

[bekemzi]

Доброго времени суток!
помогите пожалуйста разобраться с таким примером
$\sum_{l=1}^{n}\l\cdot({C}_{n}^{l})^2 $
Сначала я получил $n\cdot\sum_{l=1}^{n}{C}_{n-1}^{l-1}\cdot{C}_{n}^{l} $
Далее по треугольнику паскаля определил чему равно $ \sum_{l=1}^{n}{C}_{n-1}^{l-1}\cdot{C}_{n}^{l} $ получилось ${C}_{n}^{n}+{C}_{n+1}^{n}+...+{C}_{n+n}^{n} $
подскажите пожалуйста что с этим делать дальше ибо нет никаких соображений, у меня несколько примеров на данном этапе хотелось бы остальные сделать самостоятельно.

[hippie]

bekemzi в сообщении #725284 писал(а):

Сначала я получил $n\cdot\sum_{l=1}^{n}{C}_{n-1}^{l-1}\cdot{C}_{n}^{l} $

Остаётся заметить, что $\sum\limits_{l=1}^{n}{C}_{n-1}^{l-1}\cdot{C}_{n}^{l}\ -$ это число путей из левого нижнего угла клетчатого прямоугольника $n\times (n-1)$ в правый верхний, состоящих только из шагов вправо и вверх.

[Sonic86]

bekemzi в сообщении #725284 писал(а):

чему равно $ \sum_{l=1}^{n}{C}_{n-1}^{l-1}\cdot{C}_{n}^{l} $

Можно воспользоваться тождеством (или сверткой) Вандермонда:

$$\binom{m+n}{r}=\sum_k\binom{m}{k}\binom{n}{r-k}$$

http://en.wikipedia.org/wiki/Vandermonde%27s_identity

[bekemzi]

Простите, переформулирую вопрос, возможно ли $n\cdot({C}_{n}^{n}+{C}_{n+1}^{n}+...+{C}_{n+n}^{n})$ записать в виде некой функции что-ли, так как если раскрывать, то получится $n+\frac{n\cdot(n+1)}{1!}+\frac{n\cdot(n+1)\cdot(n+2)}{2!}+...$ или $n\cdot({C}_{n}^{n}+{C}_{n+1}^{n}+...+{C}_{n+n}^{n})$ является коечным ответом?

[Sonic86]

bekemzi в сообщении #725337 писал(а):

Простите, переформулирую вопрос, возможно ли $n\cdot({C}_{n}^{n}+{C}_{n+1}^{n}+...+{C}_{n+n}^{n})$ записать в виде некой функции что-ли, так как если раскрывать, то получится $n+\frac{n\cdot(n+1)}{1!}+\frac{n\cdot(n+1)\cdot(n+2)}{2!}+...$ или $n\cdot({C}_{n}^{n}+{C}_{n+1}^{n}+...+{C}_{n+n}^{n})$ является коечным ответом?

Формально говоря, и исходное задание суммы и оба Ваших выражения - функции от $n$. Обычно в таких задачах спрашивают о замкнутом виде формулы, т.е. о равной формуле, содержащей лишь конечное число сложений, умножений и биномиальных коэффициентов. Вы просто должны упростить выражение. Исходное выражение - однократная сумма, полученное Вами - тоже однократная сумма, так что выражение Вы не упростили полностью, а пока только преобразовали (хотя биномиальных коэффициентов внутри суммы стало меньше, так что все-таки сумму немного упростили).
Сумму ${C}_{n}^{n}+{C}_{n+1}^{n}+...+{C}_{n+n}^{n}$ можно выразить в замкнутом виде, для выражения достаточно лишь индукции и основного тождества $C_n^k=C_{n-1}^k+C_{n-1}^{k-1}$. Попробуйте.

[bekemzi]

Дико извиняюсь, но можно намекнуть как посчитать индукцию или дать ссылку на хороший материал ибо я в тупике

[Sonic86]

Попробуйте сначала построить индуктивное предположение на основании нескольких частных случаев (либо на основании свертки Вандермонда)

[TOTAL]

bekemzi в сообщении #726505 писал(а):

Дико извиняюсь, но можно намекнуть

${C}_{n}^{n}+{C}_{n+1}^{n}+...+{C}_{n+n}^{n}$ - это коэффициент при $x^n$ в сумме $(1+x)^n +(1+x)^{n+1} + \cdots + (1+x)^{2n}.$

Находите сумму геометрической прогрессии, затем находите нужный коэффициент.

[bekemzi]

Снова извините, посчитал сумму прогрессии получил $сумма=\frac{(x+1)^n\cdot ((x+1)^n-1)}{x}$,
но дальше всё плохо совсем
$(x+1)^1=1$
$(x+1)^3=3$
$((x+1)^6)+((x+1)^5)+((x+1)^4)=10$
Где-то ошибка или х страшное комплексное число

[Ms-dos4]

Вы неверно нашли сумму прогрессии. У вас же n+1 член, поэтому сумма будет
$\[\frac{{{{(1 + x)}^n}({{(1 + x)}^{n + 1}} - 1)}}{x} = \frac{1}{x}{(1 + x)^{2n + 1}} - \frac{1}{x}{(1 + x)^n}\]$
А теперь заметьте, что во втором слагаемом $\[{x^n}\]$ вообще не будет, поэтому исследуем первое
$\[\frac{1}{x}{(1 + x)^{2n + 1}} = \frac{1}{x}\sum\limits_{k = 0}^{2n + 1} {C_{2n + 1}^k{x^{2n + 1 - k}}} \]$
$\[{x^n}\]$ получится при $\[k = n\]$
Окончательно ваша сумма
$\[\sum\limits_{k = n}^{2n} {C_k^n} = C_{2n + 1}^n\]$

[sopor]

Зачем такие сложности?
$\sum\limits_{l=1}^{n} l\cdot(C_{n}^{l})^2=\frac{n}{2}\sum\limits_{l=0}^{n} (C_{n}^{l})^2=\frac{n}{2}\cdot C_{2n}^{n}$
Первое равенство следует из того, что $C_{n}^{k}=C_{n}^{n-k}$

[TOTAL]

sopor в сообщении #726678 писал(а):

Зачем такие сложности?
$\sum\limits_{l=1}^{n} l\cdot(C_{n}^{l})^2=\frac{n}{2}\sum\limits_{l=1}^{n} (C_{n}^{l})^2=\frac{n}{2}\cdot C_{2n}^{n}$
Первое равенство следует из того, что $C_{n}^{k}=C_{n}^{n-k}$

Проверьте первое равенство и второе равенство. (А ответ верный.)

[sopor]

TOTAL в сообщении #726695 писал(а):

sopor в сообщении #726678 писал(а):

Зачем такие сложности?
$\sum\limits_{l=1}^{n} l\cdot(C_{n}^{l})^2=\frac{n}{2}\sum\limits_{l=1}^{n} (C_{n}^{l})^2=\frac{n}{2}\cdot C_{2n}^{n}$
Первое равенство следует из того, что $C_{n}^{k}=C_{n}^{n-k}$

Проверьте первое равенство и второе равенство. (А ответ верный.)

Спасибо, да, индекс не тот поставил

[bekemzi]

Всем огромное спасибо!