Demostrar que $\sum_{i=0}^d {n\choose i}\leq n^d +1$

Question

Demostrar que $\sum_{i=0}^d {n\choose i}\leq n^d +1$

He intentado hacerlo por inducción. Para $d=0$ la desigualdad dice $1\leq 2$, así que es verdad.

Para la inducción paso asumimos $\sum_{i=0}^d {n\choose i}\leq n^d +1$ así tenemos $$\sum_{i=0}^{d+1} {n\choose i}\leq n^d +1 \leq n^d+1+ {n\choose {d+1}}$$ y aquí es donde estoy atascado. ¿Por qué es $n^d+{n\choose {d+1}} \leq n^{d+1}$?

Answer 1

Sugerencia: Esto es equivalente a

$${n \choose d+1} \leq n^{d+1}-n^d = n^d(n-1).$$

Ahora escribir

$${n \choose d+1} = \frac{n\cdot(n-1)\cdots(n-d)}{(d+1)!}.$$

Se puede tomar desde aquí?

(Nota: El inductivo paso te deseo de probar que no es cierto para $d=0$, por lo que debe incluir $d=1$ separado en una base de caso).

Answer 2

Para $n\geq 2$ puede utilizar $$ n^d+1\underbrace{\leq}_{n^d\geq n\geq 1} n^d+n^d=2n^d\underbrace{\leq}_{n\geq 2}n\cdot n^d=n^{d+1}. $$

Answer 3

El lado izquierdo es el número de formas de elegir cualquiera de las $0,1,\ldots,d$ $n$ sin orden y sin repitition. El lado derecho es el 1+ el número de formas de elegir los $d$ $n$ con el orden y la repetición.

El +1 se ocupa de la $0$ elección en el lado izquierdo. Incluso sin orden en la RHS, va a ser más grande: dado cualquier elección de $k\leq d$, la extendemos a una selección de $d$ con la repetición mediante la adición de elementos que ya ha elegido. Esta construcción es inyectiva. Por lo tanto $LHS \leq RHS$.