이항 계수에 대한 경계 합 [중복]

Nov 27 2020

어떻게 보여줄 수 있니 $ \sum_{k=0}^{m}\binom{n}{k} \leq (n+1)^m$ ...에 대한 $m \leq n $?

답변

1 martycohen Nov 27 2020 at 05:02

$(n+1)^m =\sum_{k=0}^m \binom{m}{k}n^k $ 그래서 만약 $n^k\binom{m}{k} \ge \binom{n}{k} $ 우리는 끝났습니다.

$\begin{array}\\ \binom{m}{k} &=\dfrac{m!}{k!(m-k)!}\\ &=\dfrac{\prod_{j=0}^{k-1}(m-j)}{k!}\\ \dfrac{n^k\binom{m}{k}}{\binom{n}{k}} &=\dfrac{n^k\prod_{j=0}^{k-1}(m-j)}{\prod_{j=0}^{k-1}(n-j)}\\ &\ge\prod_{j=0}^{k-1}(m-j) \qquad\text{since } n^k \ge \prod_{j=0}^{k-1}(n-j)\\ &\ge 1\\ \end{array} $