Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Vollständige Induktion: Binomische Formeln

Vollständige Induktion: Binomische Formeln

Universität / Fachhochschule

Tags: Binomische Formeln, Vollständige Induktion

lichtsekunde aktiv_icon

16:12 Uhr, 14.09.2009

Hallo zusammen,

ich weiß, es gibt bereits einige Threats zum Thema, aber ich glaube das gehört zu den Dingen, wo es einfach irgendwann "klick" macht, egal wie viele Lösungswege man kennt.

Also, ich glaube eigentlich das Prinzip verstanden zu haben. Das einzige was mir Probleme bereitet ist, beim Induktionsschluss einen Ausdruck zu finden der n+1 als "n und irgendwas" ersetzt. Außerdem sind Summenzeichen und Binomialkoeffizienten/Fakultäten ganz neues Gebiet für mich, was das Verständnis in Kombination nicht gerade vereinfacht, da mir einfach die Routine im Umgang fehlt.

Also es geht um Folgendes:

$\forall n \in N$ (gibt das Mengenzeichen für die nat.Zahlen nicht) gilt $\sum_{k = 0}^{n} (\begin{matrix} n \\ k \end{matrix}) a^{k} b^{n - k} = {(a + b)}^{n}$

So:

IA: n=0

$\Rightarrow$ (richtiger Folgepfeil? ist ja nicht äquivalent oder?)

1=1 (w)

IV: Die Behauptung existiert für ein $n \in N$ .

IS: n>n+1

$\sum_{k = 0}^{n + 1} (\begin{matrix} n + 1 \\ k \end{matrix}) a^{k} b^{n + 1 - k} = {(a + b)}^{n + 1}$

So jetzt kommt der Knackpunkt. Ich will ja jetzt aus n+1 wieder n machen. Also suche ich einen Ausdruck, der den Kappes da ersetzt. Wie gesagt: Ich hab noch nie mit Binomialkoeffizienten gerechnet und weiß nicht so recht damit umzugehen.

Ich hab mir aber gedacht:

$(\begin{matrix} n + 1 \\ k \end{matrix}) = (\begin{matrix} n \\ k \end{matrix}) + (\begin{matrix} n \\ k - 1 \end{matrix})$

$a^{k} b^{n + 1 - k} = a^{k} b^{n - k} b$

Ich weiß dass ich den Ausdruck jetzt irgendwie auf beiden Seiten so erweitern muss, dass die Summengrenze wieder n ist, wobei ich jetzt nicht genau weiß, wie der Ausdruck (...) aussieht. Ich denke mir ja nur, dass er irgendwas mit meiner Überlegungen zu tun hat.

Also irgendwas so:

$\sum_{k = 0}^{n} (\begin{matrix} n \\ k \end{matrix}) a^{k} b^{n - k} + (...) = {(a + b)}^{n} + (...)$

Und die rechte Seite des Terms setze ich dann mit ${(a + b)}^{n + 1}$ gleich.

Wenn das dann das Gleiche ergibt bin ich fertig, schreibe q.e.d. drunter und kassiere volle Punkte? Oder habe ich da noch einen grandiosen Denkfehler?

Vielen Dank für eure immer sehr zuverlässige Hilfe.

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:
Binomische Formeln (Mathematischer Grundbegriff)

Online-Übungen (Übungsaufgaben) bei unterricht.de:

Binomische Formeln erkennen und anwenden

BjBot aktiv_icon

16:51 Uhr, 14.09.2009

Nach IS:n>n+1 wird es falsch, denn A(n+1) zu bilden heisst nicht, dass man jetzt ÜBERALL ein n durch n+1 ersetzen muss.

Hier in der Summe musst du lediglich die obere Grenze n durch n+1 ersetzen, aber dann nicht mehr im Term selbst.

Viel mehr musst du dann die Summe aufspalten:

\sum_{k = 0}^{n + 1} (\binom{n}{k}) a^{k} b^{n - k} = \sum_{k = 0}^{n} (\binom{n}{k}) a^{k} b^{n - k} + C_{n + 1}

wobei

C_{n + 1}

das (n+1)-te Glied der Summe ist.

Sina86

16:56 Uhr, 14.09.2009

Hi zusammen,

ich muss hier leider widersprechen, lichtsekunde hat es schon so ganz richtig aufgeschrieben, ansonsten hätte der größte Summand ja negative Exponenten... Ich würde viel mehr versuchen den Term

(a + b)^{n + 1}

aufzuspalten, also:

(a + b)^{n + 1} = (a + b)^{n} \cdot (a + b)

und über den ersten Term kann man ja dank Induktionsvoraussetzung eine Aussage machen...

Lieben Gruß
Sina

lichtsekunde aktiv_icon

16:56 Uhr, 14.09.2009

Ist das denn nicht das Selbe in grün? Ich suche ja gerade das (n+1)te Glied der Summe um es hinten dran zu hängen. Das ist ja mein (...) in dem Term.

Nur dass du (...) $C_{n + 1}$ genannt hast.

edit:

Ja, so wollte ich das dann weiterführen.

Also ich wollte

${(a + b)}^{n} + " C_{n + 1} " = {(a + b)}^{n} \cdot (a + b)$

auflösen. Nur dass ich nicht auf das veflixte C komme.

Sina86

17:04 Uhr, 14.09.2009

(a + b)^{n} \cdot (a + b) = [\sum_{k = 0}^{n} (\binom{n}{k}) a^{k} \cdot b^{n - k}] \cdot (a + b) = . . .

Ich würde erst mal nicht über dieses konkrete

C_{n + 1}

nachdenken... das entsteht von allein (du wirst nämlich später noch eine Indexverschiebung der Summe durchführen müssen), man kann es jetzt noch nicht so offensichtlich sehen... ;-)

lichtsekunde aktiv_icon

17:09 Uhr, 14.09.2009

Äh okay, dann weiß ich jetzt überhaupt nicht wie ich weiter rechnen soll :D

Ich weiß bis jetzt nicht so wirklich, wie ich mit einem Summenzeichen rechne. Kannst du mir das vllt exemplarisch zeigen oder mich auf den richtigen "Weg" führen?

BjBot aktiv_icon

17:48 Uhr, 14.09.2009

Ein letztes Mal:

A(n+1) ist sicher NICHT

\sum_{k = 0}^{n + 1} (\binom{n + 1}{k}) a^{k} b^{n + 1 - k}

und das ist wiederum offensichtlich nicht dasselbe wie

\sum_{k = 0}^{n + 1} (\binom{n}{k}) a^{k} b^{n - k}

Auf was anderes habe ich mich nicht bezogen.

lichtsekunde aktiv_icon

17:54 Uhr, 14.09.2009

Aber du kommst doch zum gleichen Schluss wie ich.

Ich verweise mal auf www.vorkurs.mathematik.rwth-aachen.de/download/VorkursGLKapitel5.pdf

Seite 78. Da ist das doch genauso. Die Grenze wird auf n+1 hochgesetzt und für alle n wird n+1 eingesetzt. Was soll daran jetzt falsch sein?

Sina86

17:58 Uhr, 14.09.2009

Ok, also, wenn ich eine Summe mit einer Summe multipliziere, dann kann ich das erst mal exemplarisch machen:

n=0

[\sum_{k = 0}^{0} (\binom{0}{k}) a^{k} b^{0 - k}] \cdot (a + b) = 1 \cdot a^{0} \cdot 1 \cdot b^{0} \cdot (a + b) = 1 \cdot (a + b) = 1 \cdot a + 1 \cdot b = \sum_{k = 0}^{1} (\binom{1}{k}) a^{k} \cdot b^{1 - k}

n=1

[\sum_{k = 0}^{1} (\binom{1}{k}) a^{k} b^{1 - k}] \cdot (a + b) = (a + b) \cdot (a + b) = (a + b)^{2} = a^{2} + 2 a b + b^{2} = \sum_{k = 0}^{2} (\binom{2}{k}) a^{k} \cdot b^{2 - k}

n=2

[\sum_{k = 0}^{2} (\binom{2}{k}) a^{k} b^{2 - k}] \cdot (a + b) = (a^{2} + 2 a b + b^{2}) \cdot (a + b) = a^{3} + 3 a^{2} b + 2 a b^{2} + b^{2} = \sum_{k = 0}^{3} (\binom{3}{k}) a^{k} \cdot b^{3 - k}

...

Nun kann man sich überlegen, was passiert, wenn man ein allgemeines n verwendet:

[\sum_{k = 0}^{n} (\binom{n}{k}) a^{k} b^{n - k}] \cdot (a + b) = \sum_{k = 0}^{n + 1} (\binom{n + 1}{k}) a^{k} b^{(n + 1) - k}

aber man stellt jetzt die berechtigte Frage, wie das genau funktioniert. Also:

[\sum_{k = 0}^{n} (\binom{n}{k}) a^{k} b^{n - k}] \cdot (a + b)

(hier geht es um zwei endliche Summen, da gilt das Distributivgesetz)

= [\sum_{k = 0}^{n} (\binom{n}{k}) a^{k} b^{n - k}] \cdot a + [\sum_{k = 0}^{n} (\binom{n}{k}) a^{k} b^{n - k}] \cdot b

(wiederum das Distributivgesetz anwenden)

= \sum_{k = 0}^{n} (\binom{n}{k}) a^{k} b^{n - k} \cdot a + \sum_{k = 0}^{n} (\binom{n}{k}) a^{k} b^{n - k} \cdot b

(Potenzgesetz

a^{b} \cdot a^{c} = a^{b + c}

verwenden)

= \sum_{k = 0}^{n} (\binom{n}{k}) a^{k + 1} b^{n - k} + \sum_{k = 0}^{n} (\binom{n}{k}) a^{k} b^{n + 1 - k}

(jetzt führe ich auf der linken Seite eine Indexverschiebung (oder auch Indexshift) durch, denn mein Ziel ist es, irgendwas aus den beiden Summen auszuklammern, damit ich die Summen wieder zusammenfassen kann)

Die Indexverschiebung ist eine reine Notationsfrage (man kann sie aber auch über vollständige Induktion beweisen :-) ). Also, wenn man eine Summe der Form

\sum_{k = 0}^{n} a_{k}

hat, kann man die Grenzen der Summe um eine gewisse Zahl

d

(für gewöhnlich 1 oder -1) ändern, und muss dann die

k

-Einträge IN der Summe entsprechend mitverändern, d.h. z.B.

\sum_{k = 0}^{n} a_{k} = \sum_{k = 1}^{n + 1} a_{k - 1}

oder

\sum_{k = 0}^{n} a_{k} = \sum_{k = - 1}^{n - 1} a_{k + 1}

wenn du mal ein wenig drüber nachdenkst (vlt für ein konkretes

n

) dann wirst du einsehen, dass diese Summen wirklich dasselbe sind...

Also bei uns:

\sum_{k = 0}^{n} (\binom{n}{k}) a^{k + 1} b^{n - k} + \sum_{k = 0}^{n} (\binom{n}{k}) a^{k} b^{n + 1 - k} = \sum_{k = 1}^{n + 1} (\binom{n}{k - 1}) a^{k} b^{n - (k - 1)} + \sum_{k = 0}^{n} (\binom{n}{k}) a^{k} b^{n + 1 - k}

= \sum_{k = 1}^{n + 1} (\binom{n}{k - 1}) a^{k} b^{n + 1 - k} + \sum_{k = 0}^{n} (\binom{n}{k}) a^{k} \cdot b^{n + 1 - k}

(jetzt kann ich die Summen susammenfügen, wo die Indizes passen, d.h auf der linken Seite nehme ich erst mal das größte und auf der rechten Seite das kleinste Glied aus der Summe raus)

= (\binom{n}{n}) a^{n + 1} \cdot b^{n + 1 - (n + 1)} + \sum_{k = 1}^{n} (\binom{n}{k - 1}) a^{k} b^{n + 1 - k} + \sum_{k = 1}^{n} (\binom{n}{k}) a^{k} \cdot b^{n + 1 - k} + (\binom{n}{0}) a^{0} \cdot b^{n + 1 - 0}

= a^{n + 1} + \sum_{k = 1}^{n} (\binom{n}{k - 1}) a^{k} b^{n + 1 - k} + (\binom{n}{k}) a^{k} \cdot b^{n + 1 - k} + b^{n + 1}

(denn es gilt

(\binom{n}{n}) = (\binom{n}{0}) = 1

, nun Distributivgesetz in der Summe)

= a^{n + 1} + \sum_{k = 1}^{n} ((\binom{n}{k - 1}) + (\binom{n}{k})) a^{k} \cdot b^{n + 1 - k} + b^{n + 1}

(nun gilt nach einem Satz folgende Formel:

(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k})

, also bei uns damit...)

= a^{n + 1} + \sum_{k = 1}^{n} (\binom{n + 1}{k}) a^{k} \cdot b^{n + 1 - k} + b^{n + 1}

Jetzt kommt noch eine Beobachtung hinzu:

a^{n + 1} = 1 \cdot a^{n + 1} b^{0} = (\binom{n + 1}{n + 1}) a^{n + 1} \cdot b^{n + 1 - (n + 1)}

(dies ist also das größte Glied der Summe)
entsprechend ist:

b^{n + 1} = 1 \cdot a^{0} b^{n + 1} = (\binom{n + 1}{0}) a^{0} \cdot b^{n + 1 - 0}

(das kleinste Glied der Summe)

Das füge ich nun hinzu, dann ist:

= a^{n + 1} + \sum_{k = 1}^{n} (\binom{n + 1}{k}) a^{k} \cdot b^{n + 1 - k} + b^{n + 1} = \sum_{k = 0}^{n + 1} (\binom{n + 1}{k}) a^{k} \cdot b^{n + 1 - k}

voilá

Der Beweis ist eigentlich eine reine Indexschlacht, in dem Sinne erst mal viel Spaß beim nachvollziehen ;-)

Lieben Gruß
Sina

Sina86

18:03 Uhr, 14.09.2009

Hallo,

vlt liegt hier eine Verwechselung vor, wenn man eine Aussage wie

(a + b)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) \cdot a^{k} \cdot b^{n - k}

beweisen soll, dann wird im Induktionsschritt JEDES

n

durch

n + 1

ersetzt (denn ich will ja zeigen, dass die Aussage auch für

n + 1

gilt, wenn sie für

n

gilt).

Bei einem Indexshift wie oben durchgeführt veränder ich nur die Grenzen der Summe, da wird aus

n

dann

n + 1

(oder anders herum), jedoch darf ich dort NICHT innerhalb der Summe das

n

ändern, sondern nur das

k

.

Gruß
Sina

lichtsekunde aktiv_icon

19:40 Uhr, 14.09.2009

puhhh alles klar. Ich werde mir das mal in Ruhe ansehen und hoffe dann da durchzusteigen, sonst kann ich ja immernoch meine Tutorin fragen ;)

Vielen Dank für den Aufwand und die Hilfe. (Jetzt weiß ich auch, dass man sowas durch Indexverschiebung lösen kann...)

Liebe Grüße

643722

643525

	Status: nicht eingeloggt	Noch nicht registriert?