N über K Element N Beweis < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:00 So 13.11.2011 | | Autor: | Catman |
| Aufgabe | | Beweisen Sie mittels vollständiger Induktion für alle n element N : (n über k) element N für alle k element {0,...,n} |
Also ich habe bei dieser Aufgabe gar keine Ahnung was ich genau zu tun habe bei der Induktion. Bisher hatten wir immer Aufgaben bei denen eine Gleichung war und wir dann die Induktionsbehauptung über die Gleichung mit der Induktionsvorraussetzung in Verbrindung bringen mussten, aber hier komm ich auf keinen guten Ansatz. Das einzige was ich habe ist die Rekursionsformel also das (n+1 über k) = (n über k-1) + (n über k). Wäre sehr dankbar für Hilfe.
Gruß
Andy
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:11 So 13.11.2011 | | Autor: | Loddar |
Hallo Catman,
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]") !!
Zu zeigen ist hier "lediglich", dass ein Bruch wie [mm] $\vektor{n\\k} [/mm] \ = \ [mm] \bruch{n!}{k!*(n-k)!}$ [/mm] auch jedesmal wieder eine natürlich Zahl aus [mm] $\IN$ [/mm] ergibt.
Mit der von Dir genannten Rekursionsformel bist Du im Induktionsschritt auch sehr schnell am gewünschten ziel, da Du auf beide "neuen" Binomialkoeffizienten jeweils die Induktionsvoraussetzung anwenden kannst.
Gruß
Loddar
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:37 Mo 14.11.2011 | | Autor: | Catman |
Mhm, also ich komme da auf keine Idee was ich tun muss, bzw. wie ich die Induktionsvorraussetzung anzuwenden habe.
Also ich schreib mal auf was ich getan habe.
Induktionsanfang:
n=1 ->
[mm] \vektor{1 \\ k} [/mm] = 1/1 (für k=0 und für k=n=1) ist wahr.
Induktionsvorraussetzung:
Für ein beliebiges, festes [mm] n\inN [/mm] gelte [mm] \vektor{n \\ k} \in [/mm] N für alle k [mm] \in [/mm] {0,...,n}
Induktionsbehauptung:
Dann ist zu zeigen, dass auch [mm] \vektor{n+1 \\ k} \in [/mm] N für alle k [mm] \in [/mm] {0,...,n} gilt.
Induktionsschluss:
[mm] \vektor{n+1 \\ k} [/mm] = [mm] \vektor{n \\ k-1} [/mm] + [mm] \vektor{n \\ k}
[/mm]
Was muss ich denn jetzt tun?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:04 Mo 14.11.2011 | | Autor: | Loddar |
Hallo Catman!
Was weißt Du denn über [mm]\vektor{n \\
k-1}[/mm] bzw. über [mm]\vektor{n \\
k}[/mm] ? Sind diese Ausdrücke [mm] $\in\IN$ [/mm] ?
Was bedeutet dies dann für die Summe?
Gruß
Loddar
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:17 Mo 14.11.2011 | | Autor: | Catman |
Also kann man eventuell sagen, dass [mm] \vektor{n \\ k} \in [/mm] N ist, weil das laut Induktionsvorraussetzung so ist? Dann müsste man nur noch zeigen, dass dasselbe für [mm] \vektor{n \\ k-1} [/mm] gilt, da die Summe 2er Zahlen [mm] \in [/mm] N ja [mm] \in [/mm] N ist. Aber wie zeige ich das für den ersten Summanden?
|
|
|
| |
|
Hallo Catman,
Du brauchst für Deine Induktion noch folgendes:
[mm] \vektor{n\\0}=\vektor{n\\n}=1
[/mm]
Das ist sozusagen der Rand des Pascalschen Dreiecks. Damit haben alle übrigen Einträge zwei obere Nachbarn und sind als deren Summe darstellbar. Und da von oben gelesen nur natürliche Zahlen vorkommen, können alle darunter auch nur natürliche Zahlen sein.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:16 Mo 14.11.2011 | | Autor: | Catman |
Danke für die Antwort. Aber aus der Beschreibung werde ich nicht wirklich schlau.
War es denn richtig, dass ich nur noch für [mm] \vektor{n \\ k-1} [/mm] zeigen muss, dass [mm] \in [/mm] N gilt?
Also und wenn das stimmt wäre es richtig eine Fallunterscheidung zu machen für k=0, k=1 und k>=1<=N ?
Dann wäre ja für k=1 mit der Definition (die in meinen Vorlesungsaufzeichnungen auch steht) die Lösung 1, also [mm] \in [/mm] N.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 01:08 Di 15.11.2011 | | Autor: | Helbig |
Hallo Catman,
Mach die Fallunterscheidung $k=0$, $k=n+1$ und [mm] $1\le [/mm] k [mm] \le [/mm] n$. Im letzten Fall kannst Du die Induktionsvoraussetzung anwenden, da dann $k$ und $k-1$ zwischen $0$ und $n$ einschließlich liegen.
Hilft das?
Grüße
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 01:19 Di 15.11.2011 | | Autor: | Catman |
Ehm im Moment komm ich damit auch nicht wirklich auf was, aber ich werde mir das Morgen nochmal intensiv anschauen. Auf jeden Fall schonmal Danke!
Nur wieso k=n+1? k kann doch nicht größer als n sein?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 01:55 Di 15.11.2011 | | Autor: | Helbig |
Du mußt [mm] ${n+1\choose k}\in\IN$ [/mm] für [mm] $0\le [/mm] k [mm] \le [/mm] n+1$ zeigen. Und die Induktionsvoraussetzung kannst Du nur für [mm] $1\le [/mm] k [mm] \le [/mm] n$ verwenden, denn nur dann ist [mm] $n\choose [/mm] {k-1}$ und [mm] $n\choose [/mm] k$ definiert.
OK?
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:32 Di 15.11.2011 | | Autor: | Catman |
Danke für die Antwort. Ist das denn wie folgt dann richtig?
Induktionsanfang:
n=1 ist wahr
Induktionsvorraussetzung:
Für ein beliebiges, festes n gelte [mm] \vektor{n \\ k} \in [/mm] N für alle k {0,...,n}
Induktionsbehauptung:
Dann ist zu zeigen, dass auch [mm] \vektor{n+1 \\ k} \in [/mm] N für alle k {0,...,n+1} gilt.
Induktionsschluss:
[mm] \vektor{n+1 \\ k} [/mm] = [mm] \vektor{n \\ k-1} [/mm] + [mm] \vektor{n \\ k}
[/mm]
laut Vorraussetzung gilt [mm] \vektor{n \\ k} \in [/mm] N also ist noch zu zeigen, dass [mm] \vektor{n \\ k-1} \in [/mm] N gilt.
Für k=1 folgt [mm] \vektor{n \\ 0} [/mm] =1 also wahr
Für k=0 folgt [mm] \vektor{n \\ -1} [/mm] =0 (da [mm] \vektor{n \\ k} [/mm] = 0 für k<0)
Also gilt für k=0 auch [mm] \in [/mm] N, da 0 + eine Zahl [mm] \in [/mm] N = eine Zahl [mm] \in [/mm] N ist.
Für 1<=k<=n+1 folgt
[mm] \vektor{n \\ k-1} [/mm] = [mm] \bruch{n!}{(k-1)!*(n-k+1)!}
[/mm]
Da k-1 >=0 ist und n-k+1>=0 (denn k kann max. n+1 sein) folgt, dass für alle k<=1<=n+1 [mm] \vektor{n \\ k-1} \in [/mm] N
Induktionsschluss
Laut Prinzip der vollständigen Induktion ist die Behauptung bewiesen.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:57 Di 15.11.2011 | | Autor: | Helbig |
> Danke für die Antwort. Ist das denn wie folgt dann
> richtig?
>
> Induktionsanfang:
>
> n=1 ist wahr
>
> Induktionsvorraussetzung:
>
> Für ein beliebiges, festes n gelte [mm]\vektor{n \\ k} \in[/mm] N
> für alle k {0,...,n}
>
> Induktionsbehauptung:
>
> Dann ist zu zeigen, dass auch [mm]\vektor{n+1 \\ k} \in[/mm] N für
> alle k {0,...,n+1} gilt.
Richtig!
>
> Induktionsschluss:
>
> [mm]\vektor{n+1 \\ k}[/mm] = [mm]\vektor{n \\ k-1}[/mm] + [mm]\vektor{n \\ k}[/mm]
>
> laut Vorraussetzung gilt [mm]\vektor{n \\ k} \in[/mm] N also ist
> noch zu zeigen, dass [mm]\vektor{n \\ k-1} \in[/mm] N gilt.
Falsch! Wir schreiben mal ausführlich, für welche $k$ ${n [mm] \choose k}\in\IN$ [/mm] und ${n [mm] \choose k-1}\in \IN$ [/mm] nach Induktionsvoraussetzung gilt. [mm] ${n\choose k}\in \IN$ [/mm] gilt nur für [mm] $0\le [/mm] k [mm] \le [/mm] n$, also nicht für $k=n+1$.
[mm] ${n\choose k-1}\in \IN$ [/mm] gilt nur für [mm] $0\le k-1\le [/mm] n$, das heißt für [mm] $1\le [/mm] k [mm] \le [/mm] n+1$, aber nicht für $k=0$.
Insgesamt kannst Du also die Induktionsvoraussetzung nur für [mm] $1\le [/mm] k [mm] \le [/mm] n$ anwenden. Die beiden Randpunkte $k=0$ und $k=n+1$ kannst Du direkt ohne Induktionsvoraussetzung angeben.
Ich hoffe das hilft weiter.
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:19 Di 15.11.2011 | | Autor: | Catman |
Vielen Dank.
Also dann hab ich jetzt folgendes beim Induktionsschluss:
für k=n+1
[mm] \vektor{n \\ n+1} [/mm] = 0 (weil das untere größer als das obere)
[mm] \vektor{n \\ n+1-1} [/mm] = 1
Also [mm] \vektor{n+1 \\ k} \in [/mm] N
für k=0
[mm] \vektor{n \\ 0} [/mm] = 1
[mm] \vektor{n \\ -1} [/mm] = 0 (weil das untere <0)
o + Zahl [mm] \in [/mm] N = Zahl [mm] \in [/mm] N
für 1<=k<=n
laut Vorraussetzung [mm] \vektor{n \\ k} \in [/mm] N
[mm] \vektor{n \\ k-1} [/mm] = [mm] \bruch{n!}{(k-1)!*(n-k+1)!}
[/mm]
(k-1)! >= 1
(n-k+1)! >= 1
n! >= 1
Daraus folgt [mm] \vektor{n \\ k-1} \in [/mm] N
So richtig?
|
|
|
| |
|
Hallo Catman,
> Also dann hab ich jetzt folgendes beim Induktionsschluss:
>
> für k=n+1
>
> [mm]\vektor{n \\
n+1}[/mm] = 0 (weil das untere größer als das
> obere)
Wo ist dieser Wert denn definiert? Das stimmt nicht.
> [mm]\vektor{n \\
n+1-1}[/mm] = 1
>
> Also [mm]\vektor{n+1 \\
k} \in[/mm] N
>
> für k=0
>
> [mm]\vektor{n \\
0}[/mm] = 1
>
> [mm]\vektor{n \\
-1}[/mm] = 0 (weil das untere <0)
Gleiche Frage wie oben: wo ist das so definiert?
> o + Zahl [mm]\in[/mm] N = Zahl [mm]\in[/mm] N
>
> für 1<=k<=n
>
> laut Vorraussetzung [mm]\vektor{n \\
k} \in[/mm] N
Voraussetzung hat nur ein "r".
> [mm]\vektor{n \\
k-1}[/mm] = [mm]\bruch{n!}{(k-1)!*(n-k+1)!}[/mm]
>
> (k-1)! >= 1
> (n-k+1)! >= 1
> n! >= 1
>
> Daraus folgt [mm]\vektor{n \\
k-1} \in[/mm] N
Wieso folgt das daraus, dass alle drei Fakultäten [mm] \ge1 [/mm] sind? Auch das stimmt nicht.
> So richtig?
Nein.
Induktionsvoraussetzung: für ein bestimmtes n sind alle [mm] \vektor{n\\k}\in\IN, 0\le k\le{n}, k,n\in\IN.
[/mm]
Dann ist für [mm] 1\le k\le{n} [/mm] der Binomialkoeffizient [mm] \vektor{n+1\\k}=\vektor{n\\k}+\vektor{n\\k-1} [/mm] als Summe zweier natürlicher Zahlen wieder eine natürliche Zahl.
Und für k=0 und k=n+1 gilt [mm] \vektor{n+1\\0}=\vektor{n+1\\n+1}=\bruch{(n+1)!}{(n+1)!*0!}=1\in\IN.
[/mm]
Also sind alle Binomialkoeffizienten vom Grad (n+1) ebenfalls natürliche Zahlen.
***
Dein Induktionsanfang für n=1 ist übrigens nur wahr, wenn Du Dich wirklich vergewissert hast, dass [mm] \vektor{1\\0}=\vektor{1\\1}=1. [/mm] Das ist zwar korrekt, aber Du musst eben zwei Binomialkoeffizienten überprüfen, nicht nur einen.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:53 Di 15.11.2011 | | Autor: | Catman |
In der Vorlesung haben wir aufgeschrieben:Laut Konvention gilt 0!=1 und daher [mm] \vektor{n \\ 0} [/mm] = 1 = [mm] \vektor{n \\ n}. [/mm] Außerdem gelten laut Konvention [mm] \vektor{n \\ k} [/mm] = 0 für k>n und k<0.
Mit dieser Annahme müsste das doch stimmen oder nicht?
|
|
|
| |
|
Hallo nochmal,
wenn Du die zweite (unübliche) Konvention schon einmal früher als Vorlesungsstoff zitiert hättest, wäre diese Diskussion längst erledigt gewesen, denn damit hast Du die Lösung ja vorliegen.
Ansonsten habe ich Dir vorgemacht, wie es auch ohne das geht.
Wolfgangs Tipp zu den beiden "äußeren" Bin.koeff. hatte ich Dir übrigens auch schon weiter oben gegeben, aber Du bist nicht darauf eingegangen.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:07 Mi 16.11.2011 | | Autor: | Catman |
Das mit den beiden äußeren Koeffizienten habe ich auch ehrlich gesagt nicht verstanden.
Aber auf jeden Fall vielen Dank für deine Mühe.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:58 Mi 16.11.2011 | | Autor: | reverend |
Hallo Catman,
dann schau Dir doch mal das ![[]](/images/popup.gif) Pascalsche Dreieck an, wie auch schon empfohlen.
Jeder BK ist die Summe der beiden über ihm stehenden.
Außer für die BK am Rand des Dreiecks; da funktioniert die Definition nicht oder nur durch Einführung einer "Konvention", die keine ist.
Grüße
reverend
|
|
|
|
