Binomialkoeffizienten und vollständige Induktion

Neue Frage »

26.10.2006, 10:24	xX\|Guest	Auf diesen Beitrag antworten »
Binomialkoeffizienten und vollständige Induktion Hey Leute, Ich hab da folgende Aufgabe nicht verstanden und hoffe es kann mir einer erklären wie die geht: Man beweise durch vollständige Induktion: Für natürliche Zahlen 0 $\begin{eqnarray} \leq \end{eqnarray}$ m $\begin{eqnarray} \leq \end{eqnarray}$ n gilt: $\begin{eqnarray} \sum_{k=m}^n~k \end{eqnarray}$ $\begin{eqnarray} \begin{pmatrix} k \\ m \end{pmatrix} \end{eqnarray}$ = $\begin{eqnarray} \begin{pmatrix} n+1 \\ m+1 \end{pmatrix} \end{eqnarray}$ Dabei sind $\begin{eqnarray} \begin{pmatrix} n \\ m \end{pmatrix} \end{eqnarray}$ Binomialkoeffizienten. Wie bitte soll ich an die Aufgabe herangehen?
26.10.2006, 11:32	klarsoweit	Auf diesen Beitrag antworten »
RE: Binomialkoeffizienten und vollständige Induktion Eben durch vollständige Induktion. Wie wäre es mit dem Induktionsanfang?
26.10.2006, 18:48	Mathespezialschüler	Auf diesen Beitrag antworten »
Verschoben Meinst du evtl. $\begin{eqnarray} \sum_{k=m}^n~{k\choose m}={n+1\choose m+1} \end{eqnarray}$ ? Deine Aussage ist nämlich falsch ... Gruß MSS
26.10.2006, 19:38	xX\|Guest	Auf diesen Beitrag antworten »
Ja, @ MSS: Ich meinte natürlich das ohne k davor. @ klarsoweit: Das ist ja mein Problem, ich versteh das allgemein überhaupt nicht... Der Induktionsanfang wäre demnach doch zu zeigen, dass die Aussage für eine 'erste' natürliche Zahl n gilt, also nehm ich für n = 0 oder 1 (zumindest war es so in den Vorlesungen immer) Aber wie genau zeig ich denn jetzt, dass die Aussage für n gilt? dieses Zeichen $\begin{eqnarray} \sum_{k=m}^n~k \end{eqnarray}$ versteh ich gar nicht, also ich weiß, dass es für eine Summe steht...aber da hört es auch schon auf...
26.10.2006, 21:07	Ambrosius	Auf diesen Beitrag antworten »
$\begin{eqnarray} \sum_{k=1}^n~k = 1+2+3+...+n \end{eqnarray}$ Das ist die Summe, beginnend bei k=1 bis k=n, also die Summe der ersten n natürlichen Zahlen Das ist im Übrigen gleichbedeutend mit $\begin{eqnarray} \sum_{i=1}^n~i \end{eqnarray}$ Zur Induktion: Du setz zunächst n =1. Und zeigst, das die Gleichung auch wirklich wahr ist. das heißt auf beiden seiten das gleiche steht.
26.10.2006, 21:20	xX\|Guest	Auf diesen Beitrag antworten »
Sorry aber irgendwie steh ich immer noch voll auf dem Schlauch... Die Summe von k über m soll ich im ersten Schritt also beweisen? Wenn $\begin{eqnarray} \sum_{k=1}^n~k \end{eqnarray}$ = 1 + 2 + 3 + ... + n ist, heißt das in meinem Fall also, dass $\begin{eqnarray} \sum_{k=m}^n \end{eqnarray}$ $\begin{eqnarray} \begin{pmatrix} k \\ m \end{pmatrix} \end{eqnarray}$ = was? Also ich weiß jetzt nicht genau wo ich für n 1 einsetzen soll...damit ich beweisen kann, dass die Aussage wahr ist...sorry
Anzeige

28.10.2006, 13:29	xX\|Guest	Auf diesen Beitrag antworten »
Also ich hab mir da nochmal Gedanken drüber gemacht und vllt stimmt mein Ansatz ja, also... $\begin{eqnarray} \sum_{k=m}^n~k \end{eqnarray}$ $\begin{eqnarray} \begin{pmatrix} k \\ m \end{pmatrix} \end{eqnarray}$ = $\begin{eqnarray} \begin{pmatrix} n+1 \\ m+1 \end{pmatrix} \end{eqnarray}$ Induktionsanfang: n = m $\begin{eqnarray} \sum_{k=m}^n~k \end{eqnarray}$ $\begin{eqnarray} \begin{pmatrix} k \\ n \end{pmatrix} \end{eqnarray}$ = $\begin{eqnarray} \begin{pmatrix} n+1 \\ n+1 \end{pmatrix} \end{eqnarray}$ da k = m vorgegeben ist und n = m gesetzt wurde, bekommt man: $\begin{eqnarray} \sum_{k=m}^n~k \end{eqnarray}$ $\begin{eqnarray} \begin{pmatrix} n \\ n \end{pmatrix} \end{eqnarray}$ = $\begin{eqnarray} \begin{pmatrix} n+1 \\ n+1 \end{pmatrix} \end{eqnarray}$ [wahre Aussage, da $\begin{eqnarray} \begin{pmatrix} n \\ n \end{pmatrix} \end{eqnarray}$ immer = 1 ist und $\begin{eqnarray} \begin{pmatrix} n+1 \\ n+1 \end{pmatrix} \end{eqnarray}$ auch immer = 1] Induktionsschluss: n -> n+1 $\begin{eqnarray} \sum_{k=m}^n~k \end{eqnarray}$ $\begin{eqnarray} \begin{pmatrix} n+1 \\ n+1 \end{pmatrix} \end{eqnarray}$ = $\begin{eqnarray} \begin{pmatrix} (n+1)+1 \\ (n+1)+1 \end{pmatrix} \end{eqnarray}$ [wahre Aussage, da siehe oben] stimmt das in etwa so? Oder... ich bin mir da nicht so sicher, ist ja auch nicht grad viel als Beweis mein ich.
28.10.2006, 18:12	Mathespezialschüler	Auf diesen Beitrag antworten »
Die Summe $\begin{eqnarray} \sum_{k=m}^n~{n\choose k} \end{eqnarray}$ stellst du mit "\sum_{k=m}^n~{n\choose k}" dar! Denken wir uns die ganzen überflüssigen k's also mal weg ... Der Induktionsanfang ist ok, aber beim Induktionsschluss hast du nur nochmal die Behauptung hingeschrieben, die du natürlich noch beweisen musst. Gruß MSS
29.10.2006, 21:50	Abakus	Auf diesen Beitrag antworten »
Da die Aufgabe an 2 Stellen diskutiert wird, schließe ich hier. Hier gehts weiter: Beweis mit vollständiger Induktion Grüße Abakus

Neue Frage »

Antworten »

Binomialkoeffizienten und vollständige Induktion

Verwandte Themen