Induktionsanfang n=k

21.01.2010, 01:27

AndrewWiles

Induktionsanfang n=k

Hallo,
'hab hier grade mit dem Forster Übungsbuch angefangen, die erste Aufgabe gelöst (denke ich zumindest) und stelle fest, dass sich meine Lösung von der im Buch etwas unterscheidet, und zwar:

Die Aufgabe: Seien n,k natürliche Zahlen mit $\begin{eqnarray*} n \geq k \end{eqnarray*}$ . Man beweise
$\begin{eqnarray*} \binom{n+1}{k+1}=\sum_{m=k}^{n} \binom{m}{k} \end{eqnarray*}$

Mein Induktionsanfang ist n=1, der im Buch n=k.

meine Frage: geht n=1 auch? wenn nein, warum nicht? wie und warum hätte ich darauf kommen sollen n=k als Induktionsanfang zu wählen?

21.01.2010, 01:45

Chico_Tobi

Auf diesen Beitrag antworten »

Na, versuch doch für n=1 mal den Binomialkoeffizient für _irgendein_ k zu berechnen...

Das geht nicht. Wieso? In welcher Beziehung muss die obere zur unteren Zahl eines Binomialkoeffs stehen?

21.01.2010, 02:08

AndrewWiles

Auf diesen Beitrag antworten »

Wenn ich n=1 wähle und $\begin{eqnarray*} n \geq k \end{eqnarray*}$ gilt, dan bleibt ja nur k=1 oder k=0, also $\begin{eqnarray*} \binom{2}{2}=1 \end{eqnarray*}$ oder $\begin{eqnarray*} \binom{2}{1}=2 \end{eqnarray*}$ , dachte ich.

Zitat:

In welcher Beziehung muss die obere zur unteren Zahl eines Binomialkoeffs stehen

keine Ahnung, in welcher?

21.01.2010, 04:04

El Vez

Auf diesen Beitrag antworten »

Mach Dir erstmal die zu beweisende Aussage richtig klar.
Dazu kannst Du ja mal ein paar konkrete Werte einsetzen und Dir das Ganze dann mal im Pascalschen Dreieck veranschaulichen.

Dann solltest Du sehen, dass hier eine ganz gewöhnliche Induktion über $\begin{eqnarray*} n \end{eqnarray*}$ durchzuführen ist.

Der Induktionsanfang für $\begin{eqnarray*} n=0 \end{eqnarray*}$ sollte trivial sein.

Induktionsvoraussetzung
Für ein festes $\begin{eqnarray*} n\in\mathbb N \end{eqnarray*}$ und jedes $\begin{eqnarray*} k\leq n \end{eqnarray*}$ gelte:

$\begin{eqnarray*} {{n+1} \choose {k+1}}=\sum_{m=k}^n{m \choose k}. \end{eqnarray*}$

Induktionsschritt $\begin{eqnarray*} (n\Rightarrow n+1) \end{eqnarray*}$

$\begin{eqnarray*} {{n+2} \choose {k+1}}=\ldots=\sum_{m=k}^{n+1}{m \choose k}. \end{eqnarray*}$

Jetzt ist es an Dir, die Pünktchen durch geeignete Umformungen zu ersetzen.

21.01.2010, 13:56

AndrewWiles

Auf diesen Beitrag antworten »

Näh, das's schon klar. Das geht mit dem Entwicklungssatz des Pascalschen Dreiecks, deshalb schien es mir ja auch am naheliegensten mit der Spitze n=1 zu beginnen. 's geht mir nur um den Anfang n=k.

22.01.2010, 13:00

Chico_Tobi

Auf diesen Beitrag antworten »

Du musst darüber nachdenken, für welche Paare (n,k) du die Beziehung beweisen musst, bzw. beweisen kannst.
Der Binomialkoeffizient ergibt nur Sinn, wenn n>=k. Da du die Beziehung für alle solchen Paare beweisen willst, planst du deinen Beweis so:

setze n=k, beweise, dass die aussage stimmt.
Also stimmts für alle paare wie (1,1) (2,2) (3,3).

dann zeigst du, wenn die gleichung für das paar (n,k) gilt, dann gilt sie auch für (n+1,k).

So grast du dann mit Hilfe von dem paar (1,1) die fälle (2,1) (3,1) (4,1) usw. ab.
mit Hilfe von dem paar (2,2) die fälle (3,2) (4,2) (5,2) usw.

Jetzt geschnackelt?

Nochmal von einer anderen Seite.
Du beweist mit dem Induktionsanfang n=k nicht die Aussage für _ein_ Paar, sonder für unendliche viele, nämlich für jedes k jeweils einen Induktionsanfang.

ein drittes mal, mit dem pascalschen dreieck:
du zeigst die aussage im induktionsanfang für die _gesamte_ rechte Seite, nämlich all die binomkoeffs mit n=k.

Andersrum, von deiner Seite betrachtet:
Wenn du n=1 setzt, ergibt die Aussage nur für k=1 und k=0 überhaupt einen Sinn, sonst ist nämlich der Binomialkoeffizient nicht definiert. (oder vlt null, je nachdem, wie man ihn definiert hat)
das würde bedeuten du beweist tatsächlich nur die Aussage für zwei Paare, wie willst du denn dann zeigen, dass die anderen auch drin sind? die induktion lässt dich nur in einer richtung auf dem pascalschen dreieck wandern.
Mal dir das dreieck auf, und mal mit pfeilen ein, von welchem paar auf welches andere paar du mittels induktion kommst.

Hoffe, das war jetzt nich zu viel.
Ich finds gut, dass du das verstehen willst, es ist nämlich wichtiger das System zu durchsteigen, als eine poplige Umformung durchzuführen.
Lg tobi

Neue Frage »

Antworten »

Induktionsanfang n=k

Verwandte Themen