wieder Binominalkoeffizient und vollst. Induktion

27.10.2007, 21:59

Dunkit

Auf diesen Beitrag antworten »

wieder Binominalkoeffizient und vollst. Induktion

Hallo. Nachdem das Problem von gestern nun gelöst ist habe ich direkt das nächste.
Zu zeigen ist $\begin{eqnarray*} \sum _{k=0} ^n \frac{(-1)^k}{k+1} \begin{pmatrix} n \\ k \end{pmatrix} = \frac{1}{n+1} \end{eqnarray*}$ per vollst. Indunktion.
Also auf gehts:
$\begin{eqnarray*} \sum _{k=0} ^{n+1} \frac{(-1)^k}{k+1} \begin{pmatrix} n+1 \\ k \end{pmatrix} = (\sum _{k=0} ^n \frac{(-1)^k}{k+1} \begin{pmatrix} n+1 \\ k \end{pmatrix}) + \frac{(-1)^{n+1}}{n+1+1} \end{eqnarray*}$

$\begin{eqnarray*} (\sum _{k=1} ^n \frac{(-1)^k}{k+1} \begin{pmatrix} n+1 \\ k \end{pmatrix}) + \frac{(-1)^{n+1}}{n+1+1} +1 \end{eqnarray*}$

$\begin{eqnarray*} (\sum _{k=1} ^n \frac{(-1)^k}{k+1} (\begin{pmatrix} n \\ k \end{pmatrix} + \begin{pmatrix} n \\ k-1 \end{pmatrix})) + \frac{(-1)^{n+1}}{n+1+1} +1 \end{eqnarray*}$

$\begin{eqnarray*} \sum _{k=1} ^n \frac{(-1)^k}{k+1} \begin{pmatrix} n \\ k \end{pmatrix} + \sum _{k=1} ^n \frac{(-1)^k}{k+1} \begin{pmatrix} n \\ k-1 \end{pmatrix} + \frac{(-1)^{n+1}}{n+1+1} +1 \end{eqnarray*}$

die +1 am Ende ist der k=0-te Summand der ersten Summe

$\begin{eqnarray*} \sum _{k=0} ^n \frac{(-1)^k}{k+1} \begin{pmatrix} n \\ k \end{pmatrix} + \sum _{k=0} ^{n-1} \frac{(-1)^{k+1}}{k+1+1} \begin{pmatrix} n \\ k \end{pmatrix} + \frac{(-1)^{n+1}}{n+1+1} \end{eqnarray*}$

$\begin{eqnarray*} \frac{1}{n+1} + \sum _{k=0} ^{n} \frac{(-1)^{k+1}}{k+1+1} \begin{pmatrix} n \\ k \end{pmatrix} \end{eqnarray*}$

So, jetzt weiss ich aber leider nicht mehr weiter. Habe für n=2 zumindest schonmal ausprobiert, dass die erste und die letzte zeile dasselbe ergebnis liefern... aber ich komme niocht weiter.... wenn ich mich nicht irre, muss ihc doch irgendiwe auf $\begin{eqnarray*} \frac{1}{(n+1)+1} \end{eqnarray*}$ kommen, oder?
Ich danke schonmal für eure Hilfe...

28.10.2007, 01:01

Tabea

Auf diesen Beitrag antworten »

kann es sein dass du in köln studierst und gerade das erste Übungsblatt von Analysis 1 bearbeitest? Augenzwinkern

Augenzwinkern

Ich sitze an der selben Aufgabe und bin auch genau bis dahin gekommen...

28.10.2007, 01:51

therisen

Auf diesen Beitrag antworten »

RE: wieder Binominalkoeffizient und vollst. Induktion
Es geht auch ohne Induktion:

$\begin{eqnarray*} \sum _{k=0} ^n \frac{(-1)^k}{k+1} {n \choose k} = \frac{1}{n+1} \end{eqnarray*}$

$\begin{eqnarray*} \Longleftrightarrow \sum_{k=0}^n (-1)^k {n+1 \choose k+1} = 1 \end{eqnarray*}$

$\begin{eqnarray*} \Longleftrightarrow \sum_{k=0}^{n} (-1)^k {n \choose k+1} = 1 \end{eqnarray*}$

$\begin{eqnarray*} \Longleftrightarrow -\sum_{k=1}^{n} (-1)^{k} {n \choose k} = 1 \end{eqnarray*}$

$\begin{eqnarray*} \Longleftrightarrow 1=1 \end{eqnarray*}$

Gruß, therisen

28.10.2007, 09:33

Dunkit

Auf diesen Beitrag antworten »

hi,
also von der ersten in die zweite Zeile ziehst du quasi das k+1 und n+1 in den binominalkoeffzízienten? leider hatten wir noch keinen Satz in der vorlesung, der das erlauben würde (soweit ich weiss)

und den Schritt von der vorletzten in die letzte Zeile kommt mir auch aus einem Buch bekannt vor, aber auch das hatten wir noch nicht...
Daher sollen wir die Aufgabe glaube ich auch per Induktion lösen (klang jedenfalls bei meinem Übungsleiter so...)

28.10.2007, 11:06

klarsoweit

Auf diesen Beitrag antworten »

RE: wieder Binominalkoeffizient und vollst. Induktion
Vielleicht wird es so klarer:

Wegen $\begin{eqnarray*} \frac{1}{k+1} \cdot \binom n k = \frac{n!}{(k+1) \cdot k! \cdot (n-k)!} = \frac{1}{n+1} \cdot \frac{(n+1)!}{(k+1)! \cdot ((n+1)-(k+1))!} = \frac{1}{n+1} \cdot \binom{n+1}{k+1} \end{eqnarray*}$

gilt:

$\begin{eqnarray*} \sum _{k=0}^n \frac{(-1)^k}{k+1} {n \choose k} = \sum _{k=0}^n \frac{(-1)^k}{n+1} \binom{n+1}{k+1} = \frac{1}{n+1} - \frac{1}{n+1} + \frac{1}{n+1} \cdot \sum _{k=0}^n (-1)^k \binom{n+1}{k+1} \end{eqnarray*}$

$\begin{eqnarray*} = \frac{1}{n+1} + \frac{1}{n+1} \cdot \sum _{k=-1}^n (-1)^k \binom{n+1}{k+1} = \frac{1}{n+1} + \frac{1}{n+1} \cdot \sum _{k=0}^{n+1} (-1)^{k-1} \binom{n+1}{k} \end{eqnarray*}$

$\begin{eqnarray*} = \frac{1}{n+1} + \frac{1}{n+1} \cdot (-1) \cdot \sum _{k=0}^{n+1} (-1)^{k} \binom{n+1}{k} = \frac{1}{n+1} - \frac{1}{n+1} \cdot (1 - 1)^{n+1} = \frac{1}{n+1} \end{eqnarray*}$

Tschuldigung fürs Einmischen. Augenzwinkern

Augenzwinkern

Zitat:

Original von therisen
$\begin{eqnarray*} \Longleftrightarrow \sum_{k=0}^n (-1)^k {n+1 \choose k+1} = 1 \end{eqnarray*}$

$\begin{eqnarray*} \Longleftrightarrow \sum_{k=0}^{n} (-1)^k {n \choose k+1} = 1 \end{eqnarray*}$

@therisen: diese Umformung habe ich auch nicht ganz verstanden. Zumal der letzte Summand dann $\begin{eqnarray*} (-1)^n {n \choose n+1} \end{eqnarray*}$ ist.

Aber bei den Binomialkoeffizienten ist soviel drin, da kann man nicht alles sehen.

28.10.2007, 11:18

Dunkit

Auf diesen Beitrag antworten »

oha das ist aber schon ein ganz schönes stückchen beweis ^^
mal sehen ob ich den nachher verstehe muss gleich weg...
Ich darf mal kurz anmerken, dass das das ERSTE Übungsblatt von Analysis I ist?! Da brauch ich ja stunden um dadrauf zu kommen ^^ LA war iwie einfacher Big Laugh

Big Laugh

Anzeige

28.10.2007, 11:33

therisen

Auf diesen Beitrag antworten »

RE: wieder Binominalkoeffizient und vollst. Induktion

Zitat:

Original von klarsoweit
Tschuldigung fürs Einmischen. Augenzwinkern

Augenzwinkern

Kein Problem, dein Beitrag bringt ja ein neues Licht in die Sache Wink

Wink

Zitat:

Original von klarsoweit

Zitat:

Original von therisen
$\begin{eqnarray*} \Longleftrightarrow \sum_{k=0}^n (-1)^k {n+1 \choose k+1} = 1 \end{eqnarray*}$

$\begin{eqnarray*} \Longleftrightarrow \sum_{k=0}^{n} (-1)^k {n \choose k+1} = 1 \end{eqnarray*}$

@therisen: diese Umformung habe ich auch nicht ganz verstanden. Zumal der letzte Summand dann $\begin{eqnarray*} (-1)^n {n \choose n+1} \end{eqnarray*}$ ist.

Ja, ich habe schon ein paar Zwischenschritte weggelassen. Ich forme mal die linke Seite etwas ausführlicher um:

Wegen $\begin{eqnarray*} {n+1 \choose k+1}={n\choose k+1}+{n\choose k} \end{eqnarray*}$ folgt

$\begin{eqnarray*} \sum_{k=0}^n (-1)^k {n+1 \choose k+1}=\sum_{k=0}^n (-1)^k{n\choose k+1} + \underbrace{\sum_{k=0}^n(-1)^k{n\choose k}}_{=0} \end{eqnarray*}$

(Insbesondere fällt der Summand für $\begin{eqnarray*} k=n \end{eqnarray*}$ weg.)

Gruß, therisen

28.10.2007, 12:13

klarsoweit

Auf diesen Beitrag antworten »

RE: wieder Binominalkoeffizient und vollst. Induktion
Ah ja. Ich würde gerne Ausdrücke wie $\begin{eqnarray*} \binom{n}{n+1} = \frac{n!}{(n+1)! \cdot (-1)!} \end{eqnarray*}$ vermeiden. Lieber wäre mir daher die Umformung.

$\begin{eqnarray*} \sum_{k=0}^n (-1)^k {n+1 \choose k+1} = (-1)^n + \sum_{k=0}^{n-1} (-1)^k {n+1 \choose k+1} = (-1)^n + \sum_{k=0}^{n-1} (-1)^k{n\choose k+1} + \sum_{k=0}^{n-1}(-1)^k{n\choose k} \end{eqnarray*}$

$\begin{eqnarray*} = \sum_{k=0}^{n-1} (-1)^k{n\choose k+1} + \underbrace{\sum_{k=0}^{n}(-1)^k{n\choose k}}_{= 0} = 1 - 1 + \sum_{k=1}^{n} (-1)^{k-1}{n\choose k} \end{eqnarray*}$

$\begin{eqnarray*} = 1 + \sum_{k=0}^{n} (-1)^{k-1}{n\choose k} = 1 \end{eqnarray*}$

Ist aber letztlich Geschmacksfrage.

28.10.2007, 12:21

Klausii

Auf diesen Beitrag antworten »

RE: wieder Binominalkoeffizient und vollst. Induktion

Zitat:

Original von therisen

$\begin{eqnarray*} \sum_{k=0}^n (-1)^k {n+1 \choose k+1}=\sum_{k=0}^n (-1)^k{n\choose k+1} + \underbrace{\sum_{k=0}^n(-1)^k{n\choose k}}_{=0} \end{eqnarray*}$

(Insbesondere fällt der Summand für $\begin{eqnarray*} k=n \end{eqnarray*}$ weg.)

Gruß, therisen

Weil im Zähler zwangsläufig $\begin{eqnarray*} (n-n)=0 \end{eqnarray*}$ steht?

28.10.2007, 12:23

Tabea

Auf diesen Beitrag antworten »

Aber gibt es denn garkeine Möglichkeit das per vollständige Induktion zu beweisen? Also den angefangenen Beweis von Dunkid irgendwie zu Ende zu führen?

28.10.2007, 12:25

therisen

Auf diesen Beitrag antworten »

Nein, weil $\begin{eqnarray*} {n\choose k}=0 \end{eqnarray*}$ falls $\begin{eqnarray*} k>n \end{eqnarray*}$ . Dies ist einerseits aus kombinatorischer Sicht klar und andererseits folgt das unmittelbar aus der Definition

$\begin{eqnarray*} {n\choose k}=\prod_{i=1}^k \frac {n + 1 - i} i \end{eqnarray*}$

Insbesondere ist diese Definition sinnvoll, da man diese auch für komplexes $\begin{eqnarray*} n \end{eqnarray*}$ verwenden kann. Klarsoweit arbeitet anscheinend mit der Definition

$\begin{eqnarray*} {n \choose k} = \frac{n!}{k! \cdot (n-k)!} \end{eqnarray*}$

von der ich allerdings abrate (u.a. aus den oben genannten Gründen).

@Tabea) Man muss nicht alles mit Induktion beweisen - schöner ist es meistens sogar, wenn man ohne auskommt Augenzwinkern

Augenzwinkern

Gruß, therisen

28.10.2007, 12:28

Klausii

Auf diesen Beitrag antworten »

Zitat:

Original von therisen
Nein, weil $\begin{eqnarray*} {n\choose k}=0 \end{eqnarray*}$ falls $\begin{eqnarray*} k>n \end{eqnarray*}$ . Dies ist einerseits aus kombinatorischer Sicht klar und andererseits folgt das unmittelbar aus der Definition

Gruß, therisen

Woher weißt du denn das $\begin{eqnarray*} k>n \end{eqnarray*}$ ist?

28.10.2007, 12:30

therisen

Auf diesen Beitrag antworten »

Na weil der letzte Summand $\begin{eqnarray*} {n\choose n+1} \end{eqnarray*}$ ist.

28.10.2007, 12:35

Klausii

Auf diesen Beitrag antworten »

Da hast du recht.
Danke

28.10.2007, 13:14

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von therisen
Klarsoweit arbeitet anscheinend mit der Definition

$\begin{eqnarray*} {n \choose k} = \frac{n!}{k! \cdot (n-k)!} \end{eqnarray*}$

Ich bin halt noch einer von der "alten" Schule. Und damals (vor 27 Jahren) wurde diese Definition verwendet. Bei dieser Aufgabe kommt es auch darauf an, welche Definition dunkit geläufig ist.

28.10.2007, 18:39

Dunkit

Auf diesen Beitrag antworten »

also mir sind folgende Definitionen bekannt:
$\begin{eqnarray*} {n \choose k} = \frac{n!}{k! \cdot (n-k)!} \end{eqnarray*}$
und
$\begin{eqnarray*} \begin{pmatrix} n \\ k \end{pmatrix} = \frac{1}{k!} \prod ^{k-1} _{j=0} (n-j) \end{eqnarray*}$
Ich danke erstmal noch für eure Hinweise, auch wenn ich langsam echt durcheinander komme Big Laugh

Big Laugh

Vielleicht habe ich meinen Übungsleiter auch falsch verstanden und der Tip mit der vollst. Induktion bezog sich auf eine andere Aufgabe
Ich werde mich gleich nochmal genau mit euren Tips auseinandersetzen und melde mich dann wieder Augenzwinkern

Augenzwinkern

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »