Vollständige Induktion

16.12.2009, 07:45

ankasztaj

Auf diesen Beitrag antworten »

Vollständige Induktion

Folgende Aufgabe:

[attach]12578[/attach]

Wir müssen also eine Induktion über m und über k machen.
Ich habe mit der über m angefangen
Mein Induktionschritt siehr wie folgt aus:

Erstmal linke Seite umformen:

$\begin{eqnarray*} \frac{1}{(m+1)!} (\sum\limits_{i=0}^k a_i )^{m+1} = \frac{1}{m!} (\sum\limits_{i=0}^k a_i )^{m} (\sum\limits_{i=0}^k a_i )\frac{1}{m+1} \end{eqnarray*}$

Nun die Induktionsvoraussetzung einsetzen:

$\begin{eqnarray*} = \sum\limits_{\sum\limits_{i=0}^k \alpha_i = m } \prod_{i=0}^k \frac{a_i^{\alpha_i}}{\alpha_i!} \cdot (\sum\limits_{i=0}^k a_i )\frac{1}{m+1} \end{eqnarray*}$

Jetzt habe ich mich erstmal auf einen Summanden der großen Summe konzentriert. Also einen Produkt mit der kleinen Summe ausmultipliziert

$\begin{eqnarray*} \prod_{i=0}^k \frac{a_i^{\alpha_i}}{\alpha_i!} \cdot (\sum\limits_{i=0}^k a_i )\frac{1}{m+1}= \sum_{j=0}^k \prod_{i=0}^k \frac{a_i^{\alpha_i}}{\alpha_i!}a_j \frac{1}{m+1} = \sum_{j=0}^k \prod_{i=0}^k \frac{a_i^{\alpha_i}}{\alpha_i!}\cdot \frac{\alpha_j + 1}{m+1} \cdot \frac{a_j^{\alpha_j + 1}}{(\alpha_j +1)!}<br /> \end{eqnarray*}$

So jetzt kommt es in die große Summe mit rein:

$\begin{eqnarray*} = \sum_{\sum_{i=0}^k \alpha_i =m} \sum_{j=0}^k \frac{\alpha_j + 1}{m+1}\prod_{i=0}^k \frac{a_i^{\alpha_i}}{\alpha_i!} \cdot \frac{a_j^{\alpha_j + 1}}{(\alpha_j +1)!} \end{eqnarray*}$

Und ab hier komme ich nicht weiter. Ist bis jetzt alles richtig? Wenn nicht was habt ihr für verbesserungsvorschläge?

als tipp für die gesamte aufgabe wurde uns gesagt dass man zuerst ne induktion entweder über m oder über k macht und dann im induktionsschritt über den anderen index.

hab ich die stelle bereits verpasst? also wo ich es über k machen sollte oder kommt es erst.

danke!!!

16.12.2009, 12:08

ankasztaj

Auf diesen Beitrag antworten »

RE: Vollständige Induktion
Hilfe!

16.12.2009, 20:01

ankasztaj

Auf diesen Beitrag antworten »

RE: Vollständige Induktion
ist es denn soo schwer? mensch... wie soll ich es denn alleine hinkriegen?

16.12.2009, 22:15

AD

Auf diesen Beitrag antworten »

Bis hierhin stimmt's noch

Zitat:

Original von ankasztaj
$\begin{eqnarray*} \prod_{i=0}^k \frac{a_i^{\alpha_i}}{\alpha_i!} \cdot (\sum\limits_{i=0}^k a_i )\frac{1}{m+1}= \sum_{j=0}^k \prod_{i=0}^k \frac{a_i^{\alpha_i}}{\alpha_i!}a_j \frac{1}{m+1} \end{eqnarray*}$

danach wird's völlig falsch.

Halten wir mal fest, was im Induktionsschritt $\begin{eqnarray*} m\to m+1 \end{eqnarray*}$ denn eigentlich noch nachzuweisen ist, nach deinen Vorbetrachtungen:

$\begin{eqnarray*} \left( \sum\limits_{\sum\limits_{i=0}^k \alpha_i = m} \prod_{i=0}^k \frac{a_i^{\alpha_i}}{\alpha_i!} \right) \cdot \left( \sum\limits_{i=0}^k a_i \right) \cdot\frac{1}{m+1} \stackrel{!}{=} \sum\limits_{\sum\limits_{i=0}^k \beta_i = m+1} \prod_{i=0}^k \frac{a_i^{\beta_i}}{\beta_i!} \end{eqnarray*}$

Alles in allem handelt es sich dabei "nur" um einen Koeffizientenvergleich für den Faktor vor $\begin{eqnarray*} \prod_{i=0}^k a_i^{\beta_i} \end{eqnarray*}$ , und das für jedes mögliche Index-Tupel $\begin{eqnarray*} (\beta_0,\ldots,\beta_k) \end{eqnarray*}$ :

Welche nach dem Ausmultiplizieren links entstehenden Summanden gehören zu diesem Potenzprodukt? Immer schön die Übersicht behalten. Augenzwinkern

Augenzwinkern

16.12.2009, 22:42

ankasztaj

Auf diesen Beitrag antworten »

und wie macht man einen koeffizientenvergleich?
und was meinst du mit dem faktor davor? die summe?

die letzen sätze gingen mir bisschen zu schnell

16.12.2009, 22:47

AD

Auf diesen Beitrag antworten »

Das war ja auch keine Rechnung, sondern nur die Grobstrategie, wie vorzugehen ist.

Ehe ich hier gleich alles verrate (denn das wäre der nächste Schritt, denn es ist ja nicht mehr viel zu tun) schaust du dir mal ein paar Beispiele an, also für kleine $\begin{eqnarray*} k,m \end{eqnarray*}$ , z.B. $\begin{eqnarray*} m=3,k=2 \end{eqnarray*}$ oder vielleicht noch etwas größer. Dann verstehst du vielleicht das, was eben "ein bisschen zu schnell" ging. Es ist nämlich das Grundübel, dass die Leute viel zu wenig Beispiele anschauen, um das Problem verstehend zu durchdringen.

Anzeige

16.12.2009, 23:22

Grüner

Auf diesen Beitrag antworten »

RE: Vollständige Induktion
das hier ist ganz hilfreich:

http://en.wikipedia.org/wiki/Multinomial_theorem#Proof

Augenzwinkern

Augenzwinkern

hat mir zumindest die erleuchtung gebracht.

16.12.2009, 23:30

AD

Auf diesen Beitrag antworten »

Geht auch - wobei das dann allerdings Induktion über $\begin{eqnarray*} k \end{eqnarray*}$ statt wie oben über $\begin{eqnarray*} m \end{eqnarray*}$ bedeutet. Augenzwinkern

Augenzwinkern

17.12.2009, 00:23

Grüner

Auf diesen Beitrag antworten »

muss man nicht eh über m und k induzieren?

17.12.2009, 06:31

ankasztaj

Auf diesen Beitrag antworten »

RE: Vollständige Induktion
Also ein Beispiel mit genau diesen Zahlen also k=2 und m=3 hab ich mir schon angeschaut. Ich weiß was da ungefähr vorgeht. Den nächsten Schritt sehe ich aber trotzdem nicht unglücklich

unglücklich

17.12.2009, 06:49

AD

Auf diesen Beitrag antworten »

"Hab's versucht, aber hat nichts gebracht" - so redest du dich jetzt nicht heraus. unglücklich

unglücklich

Die linke Seite von

$\begin{eqnarray*} \left( \sum\limits_{\sum\limits_{i=0}^k \alpha_i = m} \prod_{i=0}^k \frac{a_i^{\alpha_i}}{\alpha_i!} \right) \cdot \left( \sum\limits_{i=0}^k a_i \right) \cdot\frac{1}{m+1} \end{eqnarray*}$

sieht für m=3,k=2 so aus:

$\begin{eqnarray*} \frac{1}{4} \cdot \left( \frac{a_0^3}{6} + \frac{a_0^2a_1}{2} + \frac{a_0^2a_2}{2} + \frac{a_0a_1^2}{2} + a_0a_1a_2 + \frac{a_0a_2^2}{2} + \frac{a_1^3}{6} + \frac{a_1^2a_2}{2} + \frac{a_1a_2^2}{2} + \frac{a_2^3}{6} \right) \cdot (a_0+a_1+a_2) \end{eqnarray*}$

Dann wird ausmultipliziert, dann entsteht rechts u.a. das Potenzprodukt $\begin{eqnarray*} a_0^2a_2^2 \end{eqnarray*}$ . Wie setzt sich, durch das Ausmultiplizieren entstanden, der zugehörige Koeffizient dafür zusammen. Und dann das ganze gleich nochmal für $\begin{eqnarray*} a_0^2a_1a_2 \end{eqnarray*}$ , und vielleicht noch weitere Terme.

Was kannst du aus diesen Beispielen für den allgemeinen Fall herauslesen?

17.12.2009, 07:29

ankasztaj

Auf diesen Beitrag antworten »

koeffizient ist doch das was vor der variable steht oder?

also wäre das einmal $\begin{eqnarray*} \frac {1}{8} \end{eqnarray*}$ und $\begin{eqnarray*} \frac {1}{4} \end{eqnarray*}$

oder vertausche ich da gerade was?

17.12.2009, 07:33

ankasztaj

Auf diesen Beitrag antworten »

bei den beiden könnte aber statt 8 und 4 im nenner auch 2! * 2! und 2! * 1! * 1! stehen

komme ich der sache schon näher?

17.12.2009, 07:47

AD

Auf diesen Beitrag antworten »

Zitat:

Original von ankasztaj
bei den beiden könnte aber statt 8 und 4 im nenner auch 2! * 2! und 2! * 1! * 1! stehen

Jetzt kommst du der Sache langsam näher!

Laaangsam aufschreiben, wie das ganze entsteht:

Zu $\begin{eqnarray*} a_0^2a_1a_2 \end{eqnarray*}$ :

$\begin{eqnarray*} \frac{1}{4} \left( a_0a_1a_2 \cdot a_0 + \frac{a_0^2a_2}{2} \cdot a_1 + \frac{a_0^2a_1}{2} \cdot a_2 \right) = \frac{1}{4} \cdot \frac{a_0^2a_1a_2}{2!1!1!} \cdot (2 + 1 + 1) = \frac{a_0^2a_1a_2}{2!1!1!} \end{eqnarray*}$

Und zu $\begin{eqnarray*} a_0^2a_2^2 \end{eqnarray*}$ :

$\begin{eqnarray*} \frac{1}{4} \left( \frac{a_0a_2^2}{2} \cdot a_0 + 0 \cdot a_1 + \frac{a_0^2a_2}{2} \cdot a_2 \right) = \frac{1}{4} \cdot \frac{a_0^2a_2^2}{2!0!2!} \cdot (2 + 0 + 2) = \frac{a_0^2a_2^2}{2!0!2!} \end{eqnarray*}$

Jetzt denkst du aber mal ruhig, genau und sorgfältig darüber nach, auch warum und wie begründbar ich das so und nicht anders aufgeschrieben habe...

17.12.2009, 07:59

ankasztaj

Auf diesen Beitrag antworten »

Ich soll aber auch eine Induktion über k machen. Und zwar in dem Induktionsschrit von der Induktion über m.

An welcher Stelle soll ich denn das einbauen??? Am Ende wenn ich schon m->m+1 bewiesen hab oder eher??

17.12.2009, 08:13

ankasztaj

Auf diesen Beitrag antworten »

Also.... ich verstehe das so:

beim ersten bsp haben 2 summanden eine 2 im nenner. du hast dann alles in der klammer auf einen nenner gebracht und dann die koeffizienten ausgeklammert.

und die koeffizienden inder klammer sind dann $\begin{eqnarray*} \alpha_0 \alpha_1 \alpha_2 \end{eqnarray*}$

und was ist denn mit der induktion über k?

17.12.2009, 08:31

ankasztaj

Auf diesen Beitrag antworten »

Das ist dann meine Vorstellung der allg. Form

$\begin{eqnarray*} \frac{1}{m+1} \cdot \sum ((\prod_{i=0}^k \frac{a_i^{\alpha_i}}{\alpha_i!}) \cdot (\sum\limits_{i=0}^k \alpha_i) ) \end{eqnarray*}$

jetzt muss man noch was mit der summe der alpha machen und auch mit dem 1/m+1

wie soll ich es denn umändern damit summe aus alpha_i jetzt gleich m+1 ?

17.12.2009, 19:02

AD

Auf diesen Beitrag antworten »

Es ist jammerschade, dass du aus dem Beispiel (was du auch nicht selbst hier aufgeschreiben hast) nichts für den allgemeinen Fall ableitest - diese Inaktivität nervt allmählich.

Schau dir die ausgeklammerte Summe in den zwei Beispielen an: Die ist immer gleich 4, d.h. $\begin{eqnarray*} m+1 \end{eqnarray*}$ . Und das gilt allgmein, das musst du "nur" noch ordentlich aufschreiben: Zum Term

$\begin{eqnarray*} a_0^{\alpha_0} \cdot a_1^{\alpha_1} \cdot \ldots a_k^{\alpha} \end{eqnarray*}$

auf der rechten Seite (d.h. für $\begin{eqnarray*} m+1 \end{eqnarray*}$ ) tragen die Terme

$\begin{eqnarray*} \left( a_0^{\alpha_0-1} \cdot a_1^{\alpha_1} \cdot \ldots a_k^{\alpha_k} \right) \cdot a_0 \end{eqnarray*}$ , falls $\begin{eqnarray*} \alpha_0 > 0 \end{eqnarray*}$

$\begin{eqnarray*} \left( a_0^{\alpha_0} \cdot a_1^{\alpha_1-1} \cdot \ldots a_k^{\alpha_k} \right) \cdot a_1 \end{eqnarray*}$ , falls $\begin{eqnarray*} \alpha_1 > 0 \end{eqnarray*}$

...

$\begin{eqnarray*} \left( a_0^{\alpha_0} \cdot a_1^{\alpha_1} \cdot \ldots a_k^{\alpha_k-1} \right) \cdot a_k \end{eqnarray*}$ , falls $\begin{eqnarray*} \alpha_k > 0 \end{eqnarray*}$

bei. Die Vorfaktoren vor den Termen habe ich weggelassen, die kannst du dir selber besorgen. Dann alles auf einen Hauptnenner bringen, summieren, vereinfachen, schon bist du fertig. Aber tu endlich was, tu was, statt immer nur dieses "wie geht es weiter". unglücklich

unglücklich

P.S.: Bei dem Weg hier ist Induktion über k unnötig, da sowohl Induktionsanfang m=0 als auch der obige Induktionsschritt für alle k ausgeführt wird.

18.12.2009, 01:59

ankasztaj

Auf diesen Beitrag antworten »

Danke für die Antwort.

Problem ist dass ich schon mehrere Stunden an der Aufgabe saß und nicht vorwärts kam. Vielleicht gehe ich an die Aufgaben falsch ran. Keine Ahnung. Ich will aber grundsätzlich nicht dass irgendjemand alles für mich macht.
Ich will es immer verstehen smile

smile

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »