TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 177

Aus VoWi
Wechseln zu: Navigation, Suche

Berechnen Sie unter Benützung des Binomischen Lehrsatzes (und ohne Benützung der Differentialrechnung):

\sum_{k=0}^n \binom{n}{k} k 4^k

Hilfreiches[Bearbeiten]

Binomialkoeffizient[Bearbeiten, WP, 2.03 Definition]

\forall n,k\in\mathbb{N}, k\leq n:\qquad\binom{n}{k}=\frac{n!}{k!(n-k)!}

Äquivalente Definition (Merkregel):

\binom{n}{k}=
\frac{\overbrace{n\cdot(n-1)\cdot(n-2)\cdots(n-k+1)}^{k\;\text{Glieder}}}
{\underbrace{1\cdot2\cdots k}_{k\;\text{Glieder}}}

Spezialfall: \tbinom{n}{0}:=1

Binomischer Lehrsatz[Bearbeiten, WP, 2.05 Satz]

Für n \ge 0 und beliebige x, y \in \mathbb{C}:

\sum_{k=0}^n \binom{n}{k}x^{n-k} y^{k} = (x+y)^n

Lösung[Bearbeiten]

Der Term muss so umgewandelt werden, dass der Binomische Lehrsatz angewendet werden kann.

\sum_{k=0}^n k\binom{n}{k} 4^k = \underbrace{0\binom{n}{0} 4^0}_{=0} + \sum_{k=1}^n k\binom{n}{k} 4^k = \sum_{k=1}^n k\binom{n}{k} 4^k = \ldots

Dazu muss zuerst in einer Nebenrechnung k in den Binomialkoeffizient "hineinmultipliziert" werden:
k \binom{n}{k} = \frac{n!}{k!(n-k)!}\cdot k = \frac{n\cdot (n-1)!}{(k-1)!(n-k)!} = n \frac{(n-1)!}{(k-1)!(\underbrace{n-k+1-1}_{\left(n-1\right)-\left(k-1\right)})!} = n \binom{n-1}{k-1}

Dieses Ergebnis setzen wir nun in den Term ein und durch Indexverschiebung k = k-1 wird daraus dann:

\ldots = \sum_{k=1}^n n \binom{n-1}{k-1} 4^k = n \sum_{k=1}^n \binom{n-1}{k-1} 4^k = n \sum_{k=0}^{n-1} \binom{n-1}{k}4^{k+1} = 4n \sum_{k=0}^{n-1} \binom{n-1}{k}4^k

Jetzt kann man den Binomischen Lehrsatz benutzen, in dem man x = 1, y = 4 und n = n - 1 setzt:

\sum_{k=0}^{n-1} \binom{n-1}{k}1^{n-1-k} 4^{k}= \sum_{k=0}^{n-1} \binom{n-1}{k}4^{k} = (1+4)^{n-1}

Daher folgt jetzt unser Ergebnis:

\sum_{k=0}^n k\binom{n}{k} 4^k = \ldots = 4n \underbrace{\sum_{k=0}^{n-1} \binom{n-1}{k}4^{k}}_{=(1+4)^{n-1}}=4n (1+4)^{n-1}

Allgemeine Lösung[Bearbeiten]

Wenn man in der obigen Rechnung statt 4 immer den Paramter N hinschreibt, kommt man auf genau demselben Rechnenweg wie oben auf dieses allgemeinere Ergebnis:

\sum_{k=0}^n k\binom{n}{k} N^k = N\cdot (N+1)^{n-1}n

Das ist deshalb toll, da man dann auch gleich die Beispiele 151, 152 und 153 miterledigt hat:

151: N=5 \Rightarrow \sum_{k=0}^n k\binom{n}{k} 5^k=5\cdot (5+1)^{n-1} n

152: N=-1 \Rightarrow \sum_{k=0}^n k\binom{n}{k}(-1)^k=(-1)\cdot (-1+1)^{n-1} n = 0

153: \sum_{k=0}^n \binom{n}{k}(n-k)2^k = n\underbrace{\sum_{k=0}^n \binom{n}{k}2^k}_{=(1+2)^n} - \underbrace{\sum_{k=0}^n k\binom{n}{k}2^k}_{(N=2)} =\ldots \ldots = 3^n n -2\cdot 3^{n-1}n = n(3\cdot 3^{n-1} - 2\cdot 3^{n-1}) = 3^{n-1}n(3-2)=3^{n-1}n

--PurpleHaze 22:40, 16. Nov 2008 (CET)

Links[Bearbeiten]