Beweis: n über k immer ganzzahlig

26.11.2007, 20:23

Klappergrasmuecke

Beweis: n über k immer ganzzahlig

Hallo Leute, ich soll beweisen, dass für $\begin{eqnarray*} n \in \mathbb{N}_0 \end{eqnarray*}$ gilt:
$\begin{eqnarray*} {n \choose k} \end{eqnarray*}$ ist für 0 <= k <=n immer eine natürliche Zahl. Das Ganze soll ich mit Induktion über n machen.

Der Induktionsanfang ist ja leicht.

Doch den Induktionsschluss bekomm ich nicht hin... hier komme ich nur so weit:

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

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

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

Jetzt müsste ich irgendwie zeigen, dass $\begin{eqnarray*} {n \choose k} \end{eqnarray*}$ immer vielfaches von $\begin{eqnarray*} n+1-k \end{eqnarray*}$ ist, aber wie soll ich das machen? Oder is der Ansatz schon so verkehrt?

Vielen Dank für eure Antworten im Voraus smile

26.11.2007, 20:53

Auf diesen Beitrag antworten »

Was heißt schon "verkehrt" - zumindest ist dieser Zugang wenig zielführend.

Günstiger im Induktionsschritt ist die Benutzung der vom Pascalschen Dreieck her bekannten Rekursion

$\begin{eqnarray*} \binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k} \end{eqnarray*}$

26.11.2007, 21:02

Klappergrasmuecke

Auf diesen Beitrag antworten »

danke für deine antwort smile

wenn ich diese beziehung nutze, dann muss ich zeigen, dass $\begin{eqnarray*} \binom{n}{k-1} \end{eqnarray*}$ ganzzahlig ist und da fällt mir dann so gar nichts ein...

ich hatte es schonmal mit dem ansatz versucht und gesagt:

$\begin{eqnarray*} l:=k-1 \Rightarrow \binom{n}{l} \end{eqnarray*}$ ist nach Induktionsvorausetzung auch ganzzahlig, solange k>=1 ist. aber das ist doch irgendwie quatsch oder?

26.11.2007, 21:04

Auf diesen Beitrag antworten »

Zitat:

Original von Klappergrasmuecke
wenn ich diese beziehung nutze, dann muss ich zeigen, dass $\begin{eqnarray*} \binom{n}{k-1} \end{eqnarray*}$ ganzzahlig ist und da fällt mir dann so gar nichts ein...

Du weißt schon, was Vollständige Induktion ist? Die Induktionsvoraussetzung kannst du auch auf zwei Terme anwenden...

26.11.2007, 21:07

Klappergrasmuecke

Auf diesen Beitrag antworten »

also doch das mit dem $\begin{eqnarray*} l:=k-1 \end{eqnarray*}$ ?

26.11.2007, 21:10

Auf diesen Beitrag antworten »

Also mal ganz, ganz ausführlich:

Induktionsvoraussetzung: $\begin{eqnarray*} \binom{n}{k}\in\mathbb{N} \end{eqnarray*}$ für alle $\begin{eqnarray*} k \end{eqnarray*}$ mit $\begin{eqnarray*} 0\leq k\leq n \end{eqnarray*}$

Induktionsbehauptung: $\begin{eqnarray*} \binom{n+1}{k}\in\mathbb{N} \end{eqnarray*}$ für alle $\begin{eqnarray*} k \end{eqnarray*}$ mit $\begin{eqnarray*} 0\leq k\leq n+1 \end{eqnarray*}$

Im Induktionsschritt $\begin{eqnarray*} n\to n+1 \end{eqnarray*}$ kannst du nun zumindest für $\begin{eqnarray*} 1\leq k\leq n \end{eqnarray*}$ die genannte Rekursionsformel $\begin{eqnarray*} \binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k} \end{eqnarray*}$ anwenden. Und dann sind beide (!!!) Summanden gemäß Induktionsvoraussetzung ganzzahlig, da muss nix mehr extra rumgerechnet werden!

Die "Randfälle" $\begin{eqnarray*} k=0 \end{eqnarray*}$ und $\begin{eqnarray*} k=n+1 \end{eqnarray*}$ musst du noch extra betrachten, dann ist die Sache vollständig gegessen.

26.11.2007, 21:15

Klappergrasmuecke

Auf diesen Beitrag antworten »

ja das meinte ich ja mit l:=k-1 Augenzwinkern

und für k=0 und k=n+1 ist der binomialkoeffizient dann eh gleich 1 und somit ganzzahlig oder?

26.11.2007, 21:15

Auf diesen Beitrag antworten »

Na ja doch. Freude

Ich möchte aber nochmal betonen, dass es wichtig ist, die Behauptung so wie oben zu formulieren. Die Variante

Zitat:

Sei $\begin{eqnarray*} k \end{eqnarray*}$ fest.

Induktionsvoraussetzung: $\begin{eqnarray*} \binom{n}{k}\in\mathbb{N} \end{eqnarray*}$

Induktionsbehauptung: $\begin{eqnarray*} \binom{n+1}{k}\in\mathbb{N} \end{eqnarray*}$

kann jedenfalls nicht mit demselben Induktionsschritt bewiesen werden - das sollte dir schon bewusst sein, wenn du die Induktion verstanden hast.

26.11.2007, 21:21

Klappergrasmuecke

Auf diesen Beitrag antworten »

ok, danke nochmal smile

Neue Frage »

Antworten »

Beweis: n über k immer ganzzahlig

Verwandte Themen