2014 dxdy logo

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

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




 
 Биномиальные коэффициенты
Сообщение27.06.2013, 04:33 
Здравствуйте!

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

 
 
 
 Re: Биномиальные коэффициенты
Сообщение27.06.2013, 04:55 
Никак. Это неправда.

 
 
 
 Re: Биномиальные коэффициенты
Сообщение27.06.2013, 04:58 
У Вас например какие $s$ и $m$ подходят?

 
 
 
 Re: Биномиальные коэффициенты
Сообщение27.06.2013, 05:01 
Можно ткнуть пальцем в небо и почти наверное попадете в контрпример.
Например $(m,s)$, равные: $(1,1), (1, 2), (1,3)$ ... продолжать?

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

 
 
 
 Re: Биномиальные коэффициенты
Сообщение27.06.2013, 06:59 
Otta в сообщении #740917 писал(а):
Эта зависимость не степенная по $s$, она растет быстрее и степенью $s$ оценить ее в общем случае нельзя.
Это же многочлен степени $m$.

 
 
 
 Re: Биномиальные коэффициенты
Сообщение27.06.2013, 07:21 
nnosipov в сообщении #740929 писал(а):
Это же многочлен степени $m$.

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

 
 
 
 Re: Биномиальные коэффициенты
Сообщение27.06.2013, 07:26 
Всегда верно (при натуральных), если в правой части $(s+1)^m$.
Исходное неравенство верно, когда $s\ge 2$ и $m\ge 2$ одновременно.

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

 
 
 
 Re: Биномиальные коэффициенты
Сообщение27.06.2013, 18:01 
Аватара пользователя
Индукцией по $m$, начиная с $m=2$ и воспользоваться тем, что $C_s^k\leqslant s(s+1)^k $ для любого $k=0,1,\dots, s$

 
 
 
 Re: Биномиальные коэффициенты
Сообщение27.06.2013, 21:11 
А при $s^m$ неравенство сохранится?

 
 
 
 Re: Биномиальные коэффициенты
Сообщение27.06.2013, 22:19 
Сохранится. При $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$. Дальше очевидно.

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

 
 
 [ Сообщений: 12 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group