Найти сумму биномиальных коэффициентов

[mat_student]

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

Задача.
Необходимо найти сумму ${n}\choose{0}$ + ${n-1}\choose{1}$ + ${n-2}\choose{2}$ + ...

Мое решение.
Попытаемся свести сумму из условия задачи к сумме из биномиальной теоремы.

Сумму из условия можно представить в виде $\sum_{0 \leqslant k \leqslant n}$ ${n-k}\choose{k}$

Биномиальная теорема $(x+y)^n$ = $\sum_{0 \leqslant k \leqslant n}$ ${n}\choose{k}$ $x^{k}y^{n-k}$

Для начала найдем связь между ${n-k}\choose{k}$ и ${n}\choose{k}$. Для этого заметим следующее.

${n}\choose{0}$ $\cdot$ $1 =$ ${n}\choose{0}$

${n-1}\choose{1}$ $\cdot$ $\frac{n}{(n-1)}$ $=$ ${n}\choose{1}$

${n-2}\choose{2}$ $\cdot$ $\frac{n(n-1)}{(n-2)(n-3)}$ $=$ ${n}\choose{2}$

${n-k}\choose{k}$ $\cdot$ $\frac{n(n-1) \cdot ... \cdot (n-k+1)}{(n-k)([n-k]-1) \cdot ... \cdot ([n-k]-[k+1])}$ $=$ ${n}\choose{k}$

Обозначим произведение $n(n-1) \cdot ... \cdot (n-k+1)$ через $P(n,k)$, а произведение $(n-k)([n-k]-1) \cdot ... \cdot ([n-k]-[k+1])$ через $P(n-k,k)$

Тогда

${n-k}\choose{k}$ $\cdot$ $\frac{P(n,k)}{P(n-k,k)}$ $=$ ${n}\choose{k}$

Значит

${n-k}\choose{k}$ $=$ ${n}\choose{k}$ $:$ $\frac{P(n,k)}{P(n-k,k)}$ $=$ ${n}\choose{k}$ $\cdot$ $\frac{P(n-k,k)}{P(n,k)}$

Конец моего решения

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

[nnosipov]

mat_student
Вы вычислите эту сумму для нескольких первых значений $n$. Это может подсказать план дальнейших действий.

[мат-ламер]

mat_student
Ваше решение не осилил (даже не пытался) - извините. Можно попробовать связать нахождение вашей суммы с вычислением функции $f(x)=(1+x)^n$ в точке $x=1$ . Также подумайте, какой чисто комбинаторный смысл имеет вычисляемая сумма. И конечно, предыдущая подсказка крайне полезна.

[TOTAL]

mat_student в сообщении #1518674 писал(а):

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

Найдите (вдруг выведет из тупика) коэффициент при $x^n$ в

$$\frac{1}{1-x(x+1)}=\frac{a_1}{1-b_1x}+\frac{a_2}{1-b_2x}$$

[mat_student]

Благодарю за подсказки, с вашей помощью нашел вот такую последовательность http://oeis.org/A011973 , а также отсылку к книге J. Riordan, An Introduction to Combinatorial Analysis

[мат-ламер]

мат-ламер в сообщении #1518682 писал(а):

mat_student
Ваше решение не осилил (даже не пытался) - извините. Можно попробовать связать нахождение вашей суммы с вычислением функции $f(x)=(1+x)^n$ в точке $x=1$ . Также подумайте, какой чисто комбинаторный смысл имеет вычисляемая сумма. И конечно, предыдущая подсказка крайне полезна.

Извиняюсь. Посмотрел невнимательно. Мне показалось, что надо вычислить сумму $\sum\limits_{k=0}^n C^k_n$ . А так получается последовательность чисел Фибоначчи. Надеюсь, по индукции можно доказать.

P.S. Проверил. По индукции крайне легко доказывается.

[mat_student]

Благодарю.

[arseniiv]

Каждому числу Фибоначчи $F_n$ можно сопоставить листья дерева из $n$ уровней, корень которого $A$, и из каждого $A$ на следующий уровень идёт один узел $B$, а из каждого $B$ — два узла $A$ и $B$ (два вместе, не каждого по два). Каждому биномиальному коэффициенту $\binom n m$ естественно сопоставляются все сочетания из $n$ по $m$. Попробуйте теперь найти естественное соответствие между листьями дерева и объединением множеств сочетаний, соответствующим вашей сумме!

(Вместо дерева для удобства можно взять любые другие комбинаторные объекты, естественно соответствующие $F_n$, я просто все забыл. Вместо сочетаний можно брать соответствующие двоичные строки, в сущности индикаторы подмножеств.)

-- Пн май 17, 2021 02:14:34 --

Я это предлагаю, потому что такие комбинаторные соответствия между объектами обычно приятно находить. (Так даже доказывают некоторые формулы типа вашей, для чисел, построив сначала соответствие между объектами.)

[mat_student]

arseniiv в сообщении #1518770 писал(а):

Каждому числу Фибоначчи $F_n$ можно сопоставить листья дерева из $n$ уровней, корень которого $A$, и из каждого $A$ на следующий уровень идёт один узел $B$, а из каждого $B$ — два узла $A$ и $B$ (два вместе, не каждого по два). Каждому биномиальному коэффициенту $\binom n m$ естественно сопоставляются все сочетания из $n$ по $m$. Попробуйте теперь найти естественное соответствие между листьями дерева и объединением множеств сочетаний, соответствующим вашей сумме!

(Вместо дерева для удобства можно взять любые другие комбинаторные объекты, естественно соответствующие $F_n$, я просто все забыл. Вместо сочетаний можно брать соответствующие двоичные строки, в сущности индикаторы подмножеств.)

-- Пн май 17, 2021 02:14:34 --

Я это предлагаю, потому что такие комбинаторные соответствия между объектами обычно приятно находить. (Так даже доказывают некоторые формулы типа вашей, для чисел, построив сначала соответствие между объектами.)

Отдельное спасибо за такую наводку!