Биномиальные коэффициенты

[Ward]

Здравствуйте!

Как доказать, что $C_s^0+C_s^1+\dots+C_s^m\leqslant s^m$?

[Otta]

Никак. Это неправда.

[Ward]

У Вас например какие $s$ и $m$ подходят?

[Otta]

Можно ткнуть пальцем в небо и почти наверное попадете в контрпример.
Например $(m,s)$, равные: $(1,1), (1, 2), (1,3)$ ... продолжать?

Это и из общих соображений ясно. Эта зависимость не степенная по $s$, она растет быстрее и степенью $s$ оценить ее в общем случае нельзя.

[nnosipov]

Otta в сообщении #740917 писал(а):

Эта зависимость не степенная по $s$, она растет быстрее и степенью $s$ оценить ее в общем случае нельзя.

Это же многочлен степени $m$.

[Otta]

nnosipov в сообщении #740929 писал(а):

Это же многочлен степени $m$.

А и правда. :) Обозналась.
Однако же для $m=1$ условие всегда нарушается. А остальные я сейчас не успею проверить, убегаю.

[Руст]

Всегда верно (при натуральных), если в правой части $(s+1)^m$.
Исходное неравенство верно, когда $s\ge 2$ и $m\ge 2$ одновременно.

[Ward]

Т.е. в правой части должен быть $(s+1)^m$ вместо $s^m$. Верно?
P.S. Скажите пожалуйста, а как доказать это?

[Whitaker]

Индукцией по $m$, начиная с $m=2$ и воспользоваться тем, что $C_s^k\leqslant s(s+1)^k $ для любого $k=0,1,\dots, s$

[Ward]

А при $s^m$ неравенство сохранится?

[Shadow]

Сохранится. При $2 \le m \le s$

$s^m=1+(s-1)(1+s+s^2+\cdots s^{m-1})$. Значит нужно доказать, что

$1+s+s(s-1)/2+\cdots \le 1+(s-1)+(s-1)s+\cdots$

Только второе слагаемое левой части на единичку больше чем в правой. Показываем, что $1+s+s(s-1)/2 \le 1+(s-1)+(s-1)s$. Дальше очевидно.

[Shadow]

Кстати, из-за этой глупой единички в левой части - $C_s^0$ необходимо допольнительное условие $m>1$. Без нее лучше.
$C_s^1+\cdots C_s^m \le s^m$