Beweis mittels vollständiger Induktion

13.11.2013, 03:32

Tomatensalat

Beweis mittels vollständiger Induktion

Hallo Leute,

ich muss mittels vollständiger Induktion eine Aussage beweisen, komme jedoch einfach nicht weiter. Die Aussage lautet:

$\begin{eqnarray*} \sum\limits_{i=4}^{n}{i \choose 4} = {n+1 \choose n-4} \end{eqnarray*}$

Meine Überlegung war nun, dass man das Ganze für n+1 beweisen muss, also

$\begin{eqnarray*} \sum\limits_{i=4}^{n}{i \choose 4} = {n+1+1 \choose n+1-4} \end{eqnarray*}$

und das müsste dann dem hier entsprechen:

$\begin{eqnarray*} \sum\limits_{i=4}^{n}{i \choose 4} = {n+1 \choose n-4} + {n+1 \choose 4} \end{eqnarray*}$

Ersteres habe ich dann umgeschrieben in die Rekursionsformel, sodass ich folgendes habe:

$\begin{eqnarray*} {n+1+1 \choose n+1-4} = {n+1 \choose n-4} + {n+1 \choose n-3} \end{eqnarray*}$

Hier sieht man ja schon, dass der erste Summand gleich der Induktionsannahme ist, aber was mache ich mit dem restlichen Teil? Der entspricht ja leider nicht dem, was ich oben noch habe..

Könnte mir da vielleicht jemand auf die Sprünge helfen? Wäre für jede Hilfe dankbar! smile

13.11.2013, 12:33

jimmyt

Auf diesen Beitrag antworten »

RE: Beweis mittels vollständiger Induktion
Hi,

folgendes schlage ich vor:
Es ist meiner bescheidenen Meinung nach gut, die einzelnen Schritte sauber hinzuschreiben.
Also in folgender Form:

(I.A.) Induktionanfang mit n=4: ...

(I.V.) Induktionannahme: ...

(I.B.) Induktionbehauptung: ...

(I.S.) Induktionschritt n->n+1: ...

Eine Anmerkung zu dem, was du bisher hast:

Zitat:

Original von Tomatensalat
Hallo Leute,

ich muss mittels vollständiger Induktion eine Aussage beweisen, komme jedoch einfach nicht weiter. Die Aussage lautet:

$\begin{eqnarray*} \sum\limits_{i=4}^{n}{i \choose 4} = {n+1 \choose n-4} \end{eqnarray*}$

Meine Überlegung war nun, dass man das Ganze für n+1 beweisen muss, also

$\begin{eqnarray*} \sum\limits_{i=4}^{\textcolor{red}{n}}{i \choose 4} = {n+1+1 \choose n+1-4} \end{eqnarray*}$

und das müsste dann dem hier entsprechen:

$\begin{eqnarray*} \sum\limits_{i=4}^{\textcolor{red}{n}}{i \choose 4} = {n+1 \choose n-4} + {n+1 \choose 4} \end{eqnarray*}$
...

Schau dir bitte mal die rot markierten Stellen an.
Du mußt jedes n aus der I.V. durch n+1 in der Induktionbehauptung bzw. im Induktionschritt ersetzen.
Es wäre auch ganz gut, wenn du dann irgendwann während des Induktionschrittes die I.V. einsetzt.

Tipp:
Vorüberlegung in Bezug auf den Binomialkoeffizienten:

$\begin{eqnarray*} \text{(1):} ~ \binom n k + \binom n {k+1} ~=~ \binom {n+1} {k+1} \end{eqnarray*}$

$\begin{eqnarray*} \text{(2):} ~k>n>0:~ \binom n k ~=~ 0 \qquad \text{(3):} ~ \binom n n ~=~ 1\qquad \text{(4):} ~ \binom n 0 ~=~ 1 \end{eqnarray*}$

$\begin{eqnarray*} \text{(5):} ~ \binom n {n-k} ~=~ \binom n k \end{eqnarray*}$

Das könnte eventuell nützlich sein. smile

Neue Frage »

Antworten »

Beweis mittels vollständiger Induktion

Verwandte Themen