Summe von Binomialkoeffzienten

24.09.2012, 23:08

Hobbit1812

Summe von Binomialkoeffzienten

Meine Frage:
Hallo, kann mir jemand sagen, wie ich
$\begin{eqnarray*} <br /> \sum\limits_{i=1}^d \begin{pmatrix} n \\ i \end{pmatrix} <br /> \end{eqnarray*}$
gegen $\begin{eqnarray*} n^d \end{eqnarray*}$
abschätzen kann?

Meine Ideen:
Ich wollte anfangs wie folgt abschätzen:
$\begin{eqnarray*} <br /> \sum\limits_{i=1}^d \begin{pmatrix} n \\ i \end{pmatrix} < d \cdot \begin{pmatrix} n \\ k \end{pmatrix}<br /> \end{eqnarray*}$ , wobei k der Index ist, für den $\begin{eqnarray*} \begin{pmatrix} n \\ i \end{pmatrix} \end{eqnarray*}$ maximal wird. Aber das ist schon zu grob, glaube ich.
Ansonsten habe ich irgendwie keine Idee...

24.09.2012, 23:22

HAL 9000

Auf diesen Beitrag antworten »

Vollständige Induktion über $\begin{eqnarray*} d \end{eqnarray*}$ : Anfang $\begin{eqnarray*} d=1 \end{eqnarray*}$ ist klar, und im Induktionsschritt $\begin{eqnarray*} (d-1)\to d \end{eqnarray*}$ muss für $\begin{eqnarray*} n\geq d\geq 2 \end{eqnarray*}$ dann noch

$\begin{eqnarray*} n^{d-1} + \binom{n}{d} \leq n^d \end{eqnarray*}$

nachgewiesen werden, was nicht wirklich schwer ist.

24.09.2012, 23:32

Hobbit1812

Auf diesen Beitrag antworten »

Vielen Dank! Ich bin auch gerade auf die Idee der vollständigen Induktion gekommen. Allerdings passt das für $\begin{eqnarray*} d=1 \end{eqnarray*}$ nicht ganz oder? Aber im Prinzip reicht mir dass der entsprechende Term in $\begin{eqnarray*} \mathcal{O}(n^d) \end{eqnarray*}$ liegt.

24.09.2012, 23:34

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Hobbit1812
Allerdings passt das für $\begin{eqnarray*} d=1 \end{eqnarray*}$ nicht ganz oder?

Passt doch wunderbar, da herrscht Gleichheit:

$\begin{eqnarray*} \sum_{i=1}^d \binom{n}{i} = \binom{n}{1} = n = n^1 \end{eqnarray*}$ .

24.09.2012, 23:37

Hobbit1812

Auf diesen Beitrag antworten »

Oh, da habe ich mich in der Aufgabenstellung vertan. Der Index sollte bei $\begin{eqnarray*} i=0 \end{eqnarray*}$ beginnen. Da passt es nämlich nicht mehr. Aber hat sich ja geklärt. Danke trotzdem!

Neue Frage »

Antworten »

Summe von Binomialkoeffzienten

Verwandte Themen