Beweisen durch Induktion

12.02.2011, 16:58

chillerStudent

Auf diesen Beitrag antworten »

Beweisen durch Induktion

Meine Frage:
Hallo,

ich muss folgende Matrix durch Induktion beweisen:
$\begin{eqnarray*} A^n=\begin{pmatrix} 5^{n-1} & 2*5^{n-1} \\ 2*5^{n-1} & 2*5^{n-1} \end{pmatrix} \end{eqnarray*}$

Meine Ideen:
Das Thema Induktion habe ich leider nie verstanden. Kann mir das jemand vielleicht schritt für schritt erklären?

12.02.2011, 17:07

system-agent

Auf diesen Beitrag antworten »

Du musst keine Matrix beweisen, sondern du musst diese Gleichheit beweisen.

Induktion läuft so:
Du nimmst an, dass das, was du zeigen willst, bis zu einer natürlichen Zahl $\begin{eqnarray*} k \end{eqnarray*}$ richtig ist. Mithilfe dieser Annahme zeigst du dann, dass in dem Fall das was du zeigen willst auch für $\begin{eqnarray*} k+1 \end{eqnarray*}$ richtig ist.

Das bedeutet in Worten: Weisst du dass die Behauptung für eine natürliche Zahl $\begin{eqnarray*} k \end{eqnarray*}$ wahr ist, dann ist sie auch für $\begin{eqnarray*} k+1 \end{eqnarray*}$ wahr.

Mit dem Induktionsanfang [zb $\begin{eqnarray*} n=1 \end{eqnarray*}$ ] zeigst du, dass die Behauptung wirklich einmal wahr ist.
Also für $\begin{eqnarray*} n=1 \end{eqnarray*}$ wahr und mit obigem auch für $\begin{eqnarray*} n=2 \end{eqnarray*}$ wahr.
Da für $\begin{eqnarray*} n=2 \end{eqnarray*}$ wahr, mit obigem auch für $\begin{eqnarray*} n=3 \end{eqnarray*}$ wahr.
Da für $\begin{eqnarray*} n=3 \end{eqnarray*}$ wahr, mit obigem auch für $\begin{eqnarray*} n=4 \end{eqnarray*}$ wahr.
Da für $\begin{eqnarray*} n=4 \end{eqnarray*}$ wahr, mit obigem auch für $\begin{eqnarray*} n=5 \end{eqnarray*}$ wahr.
Da für $\begin{eqnarray*} n=5 \end{eqnarray*}$ wahr, mit obigem auch für $\begin{eqnarray*} n=6 \end{eqnarray*}$ wahr.
Da für $\begin{eqnarray*} n=6 \end{eqnarray*}$ wahr, mit obigem auch für $\begin{eqnarray*} n=7 \end{eqnarray*}$ wahr.
Da für $\begin{eqnarray*} n=7 \end{eqnarray*}$ wahr, mit obigem auch für $\begin{eqnarray*} n=8 \end{eqnarray*}$ wahr.
usw usw

Also wahr für alle $\begin{eqnarray*} n\in\mathbb N \end{eqnarray*}$ .

Übrigens ist die Behauptung eigentlich leicht anders:
Sei $\begin{eqnarray*} A \end{eqnarray*}$ die Matrix $\begin{eqnarray*} \begin{pmatrix} 1 & 2 \\ 2 & 2 \end{pmatrix} \end{eqnarray*}$ . Dann gilt $\begin{eqnarray*} A^n=\begin{pmatrix} 5^{n-1} & 2*5^{n-1} \\ 2*5^{n-1} & 2*5^{n-1} \end{pmatrix} \end{eqnarray*}$ .
Aber diese Behauptung stimmt nicht.

12.02.2011, 17:19

Jonas~

Auf diesen Beitrag antworten »

Wenn du einen Satz per Induktion beweisen willst, dann zeige, dass der Satz für ein bestimmtes n gilt (meistens nimmt man n=1).
Anschließend nimmst du an, der Satz sei wahr für ein beliebiges n und du beweist (oder rechnest nach) dass er auch für n+1 gilt.
Daraus folgt, dass der Satz für alle natürlichen Zahlen n wahr ist.

Beispiel:

Du möchtest beweisen, dass
$\begin{eqnarray*} 1+2+3+...+n = \sum_{i=1}^n = \frac{n \cdot (n+1)}{2} \end{eqnarray*}$
gilt.

Für n = 1 ist die Formel offensichtlich richtig, da $\begin{eqnarray*} \frac{1 \cdot 2}{2} = 1 \end{eqnarray*}$ gilt.

Nun nimm an, die Formel sei schon für eine beliebige natürliche Zahl n bewiesen.

Jetzt musst du zeigen, dass die Formel ebenso für die Zahl n+1 gültig ist. Das geht so:

$\begin{eqnarray*} 1+2+...+n+(n+1) = \sum_{i=1}^{n+1} i = \sum _{i=1}^n i + (n+1) = \frac{n \cdot (n+1)}{2} + (n+1)= \end{eqnarray*}$

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

Q.E.D.

Nun wende dieses Beweisprinzip auf deine Aufgabe an. Du musst nur die Matrix-Multiplikation beherrschen. Das ist alles.

Gruß,
Jonas

12.02.2011, 17:31

chillerStudent

Auf diesen Beitrag antworten »

WOW, danke für eure ausführlichen Antworten!
Aber leider finde ich den Zusammenhang zwischen meiner Aufgabe nicht traurig

traurig

Also was ich jetzt verstanden habe, muss ich mehrmals versuchen für n einmal in der Ausgangsmatrix $\begin{eqnarray*} \begin{pmatrix} 1 & 2 \\ 2 & 2 \end{pmatrix} \end{eqnarray*}$ und in dieser Matrix $\begin{eqnarray*} \begin{pmatrix} 5^{n-1} & 2*5^{n-1} \\ 2*5^{n-1} & 2*5^{n-1} \end{pmatrix} \end{eqnarray*}$

beliebige zahlen einzusetzen und vergelichen ob die ergebnisse gleich sind?

12.02.2011, 17:51

Jonas~

Auf diesen Beitrag antworten »

Hallo,

poste bitte einmal die Original-Aufgabenstellung!
Die Behauptung gilt nämlich nicht für beliebige Matrizen. Irgendwelche Vorraussetzungen für die Matrix A müssen noch erfüllt sein.

12.02.2011, 18:05

system-agent

Auf diesen Beitrag antworten »

Zitat:

Original von chillerStudent
$\begin{eqnarray*} \begin{pmatrix} 1 & 2 \\ 2 & 2 \end{pmatrix} \end{eqnarray*}$

Das kann nicht die Ausgangsmatrix sein, Sorry. Das soll wohl erst für $\begin{eqnarray*} n\geq2 \end{eqnarray*}$ gelten. Diese Matrix die ich dir hier hingeschrieben habe als Ausgangsmatrix wäre diese für $\begin{eqnarray*} n=1 \end{eqnarray*}$ und dort stimmt die Behauptung nämlich dann nicht.

Anzeige

13.02.2011, 14:19

chillerStudent

Auf diesen Beitrag antworten »

Zitat:

Original von Jonas~
Hallo,

poste bitte einmal die Original-Aufgabenstellung!
Die Behauptung gilt nämlich nicht für beliebige Matrizen. Irgendwelche Vorraussetzungen für die Matrix A müssen noch erfüllt sein.

Mann beweise durch Induktion, dass
$\begin{eqnarray*} A^n=\begin{pmatrix} 5^{n-1} & 2*5^{n-1} \\ 2*5^{n-1} & 4*5^{n-1} \end{pmatrix} \end{eqnarray*}$

Sogar ich hatte ein fehler bei meinem ersten Beitrag

13.02.2011, 14:41

HAL 9000

Auf diesen Beitrag antworten »

Bevor man sowas beweisen kann, sollte man aber die Matrix kennen. Klar, aus der Behauptung ergibt sich, dass das nur $\begin{eqnarray*} A = \begin{pmatrix} 1 & 2 \\ 2 & 4 \end{pmatrix} \end{eqnarray*}$ gemeint sein kann. Aber es ist nicht gerade Aufgabe eines Beweises, von der Behauptung ausgehend die Voraussetzungen zu erraten. Augenzwinkern

Augenzwinkern

13.02.2011, 15:02

chillerStudent

Auf diesen Beitrag antworten »

Was ich jetzt so alles verstanden habe ist folgendes:

IA: n=1;
IV: $\begin{eqnarray*} A^n=\begin{pmatrix} 5^{n-1} & 2*5^{n-1} \\ 2*5^{n-1} & 4*5^{n-1} \end{pmatrix} \end{eqnarray*}$

IS: $\begin{eqnarray*} A^{n+1}=5^{(n+1)-1} & 2*5^{(n+1)-1} \\ 2*5^{(n+1)-1} & 4*5^{(n+1)-1} \end{eqnarray*}$

Bin ich auf dem richtigen Weg?

13.02.2011, 15:06

chillerStudent

Auf diesen Beitrag antworten »

Oder ist der IS der hier:

$\begin{eqnarray*} \begin{pmatrix} 5^{(n+1)-1} & 2*5^{(n+1)-1} \\ 2*5^{(n+1)-1} & 4*5^{(n+1)-1} \end{pmatrix}=\begin{pmatrix} 5^{n-1} & 2*5^{n-1} \\ 2*5^{n-1} & 4*5^{n-1} \end{pmatrix} \end{eqnarray*}$

13.02.2011, 15:46

system-agent

Auf diesen Beitrag antworten »

Du bist gewaltig auf dem Holzweg.

Wie gesagt, für den Induktionsanfang musst du zeigen dass die Matrix $\begin{eqnarray*} A \end{eqnarray*}$ gerade das ist was sich ergibt, wenn du in der Behauptung $\begin{eqnarray*} n=1 \end{eqnarray*}$ einsetzt. Das geht wirklich durch einsetzen.

Dann nimmst du an [Induktionsannahme], dass deine Behauptung wahr ist für alle natürlichen Zahlen $\begin{eqnarray*} 1\leq n\leq k \end{eqnarray*}$ . Nun zeigst du, dass in diesem Fall die Behauptung auch für $\begin{eqnarray*} k+1 \end{eqnarray*}$ wahr ist.

Also:
$\begin{eqnarray*} A^{k+1}=A^k\cdot A=?\cdot A=... \end{eqnarray*}$
und über $\begin{eqnarray*} A^k \end{eqnarray*}$ solltest du nun wegen der Induktionsannahme etwas über $\begin{eqnarray*} A^k \end{eqnarray*}$ wissen und damit das Fragezeichen ersetzen können.

Aber um es nochmals klar zu sagen:
Die Aufgabenstellung ist derart lausig dass man hier schon ziemlich viel interpretieren muss. Denn so wie sie dasteht gibt es garnichts zu beweisen [denn so wie es dasteht würde man $\begin{eqnarray*} A^n \end{eqnarray*}$ einfach durch die Matrix rechts definieren - und eine Definition braucht keinen Beweis].

13.02.2011, 16:21

chillerStudent

Auf diesen Beitrag antworten »

$\begin{eqnarray*} A^{n+1}=A^n*A=\begin{pmatrix} 5^{n-1} & 2*5^{n-1} \\ 2*5^{n-1} & 4*5^{n-1} \end{pmatrix}*\begin{pmatrix} 1 & 2 \\ 2 & 4 \\ \end{pmatrix} = \begin{pmatrix} 5*5^{n-1} & 10*5^{n-1} \\ 10*5^{n-1} & 20*5^{n-1} \end{pmatrix} \end{eqnarray*}$

Richtig?

13.02.2011, 16:30

system-agent

Auf diesen Beitrag antworten »

Ja. Und nun musst du noch deutlich machen, dass das was du gekriegt hast genau in der Form $\begin{eqnarray*} \begin{pmatrix} 5^{n} & 2\cdot5^{n} \\ 2\cdot5^{n} & 2\cdot5^{n} \end{pmatrix} \end{eqnarray*}$ ist.

Dann hast du also gezeigt, dass sich die Richtigkeit der Behauptung von einer natürlichen Zahl $\begin{eqnarray*} k \end{eqnarray*}$ auf ihren Nachfolger vererbt und weil du mit dem Induktionsanfang gezeigt hast, dass es [mindestens] einmal Richtig ist, muss die Behauptung für alle natürlichen Zahlen gelten.

13.02.2011, 16:34

chillerStudent

Auf diesen Beitrag antworten »

verwirrt

Muss ich für n irgendeine Zahl einsetzen und gucken ob das gleich raus kommt?
Also $\begin{eqnarray*} A^n=A^{n+1} \end{eqnarray*}$ ??

13.02.2011, 16:36

system-agent

Auf diesen Beitrag antworten »

unglücklich

Beachte die Potenzgesetze (!!!) und $\begin{eqnarray*} 5=5^1 \end{eqnarray*}$ und $\begin{eqnarray*} 10=2\cdot 5 \end{eqnarray*}$ und $\begin{eqnarray*} 20=4\cdot 5 \end{eqnarray*}$ . Nutze das um zu bestätigen, dass
$\begin{eqnarray*} \begin{pmatrix} 5\cdot5^{n-1} & 10\cdot5^{n-1} \\ 10\cdot5^{n-1} & 20\cdot5^{n-1} \end{pmatrix}=\begin{pmatrix} 5^{n} & 2\cdot5^{n} \\ 2\cdot5^{n} & 2\cdot5^{n} \end{pmatrix} \end{eqnarray*}$ .

13.02.2011, 17:11

chillerStudent

Auf diesen Beitrag antworten »

meinst du wirklich

$\begin{eqnarray*} \begin{pmatrix} 5\cdot5^{n-1} & 10\cdot5^{n-1} \\ 10\cdot5^{n-1} & 20\cdot5^{n-1} \end{pmatrix}=\begin{pmatrix} 5^{n} & 2\cdot5^{n} \\ 2\cdot5^{n} & 4\cdot5^{n} \end{pmatrix} \end{eqnarray*}$

oder

$\begin{eqnarray*} \begin{pmatrix} 5\cdot5^{n-1} & 10\cdot5^{n-1} \\ 10\cdot5^{n-1} & 20\cdot5^{n-1} \end{pmatrix}=\begin{pmatrix} 5^{n-1} & 2\cdot5^{n-1} \\ 2\cdot5^{n-1} & 4\cdot5^{n-1} \end{pmatrix} \end{eqnarray*}$ .

13.02.2011, 17:18

system-agent

Auf diesen Beitrag antworten »

Ja, das meine ich wirklich. Du willst doch nun auch bestätigen, dass die Behauptung im Fall $\begin{eqnarray*} n+1 \end{eqnarray*}$ wahr ist.

Ich denke du solltest dringend nochmals genauer etwas über die vollständige Induktion lesen.

13.02.2011, 17:27

chillerStudent

Auf diesen Beitrag antworten »

Ich glaub ich hab das ein klein wenig verstanden. Danke dir System-agent! Freude

Freude

Mich hat das n-1 gestört. (Potenzprobleme)

13.02.2011, 17:34

system-agent

Auf diesen Beitrag antworten »

Zur VI findest du bei Wikipedia auch gute Artikel, zb hier.

13.02.2011, 19:49

Broly

Auf diesen Beitrag antworten »

Ich meld mich auch mal zu Wort.

Habe Induktion ebenfalls noch nie gehabt.
Fasse mal zusammen ob ich das richtig verstanden habe.
Im großen geht es darum eine Formel oder Gesetzmäßigkeit die man bisher annimmt zu beweisen.

Ich habe die Matrix

$\begin{eqnarray*} A=\begin{pmatrix} 1&2 \\ 2&4 \end{pmatrix} \end{eqnarray*}$

und die Annahme das dafür
$\begin{eqnarray*} A^n=\begin{pmatrix} 1\cdot 5^{n-1}&2\cdot 5^{n-1} \\ 2\cdot 5^{n-1}&4\cdot 5^{n-1} \end{pmatrix} \end{eqnarray*}$ gillt.

A ist ja nichts anderes als $\begin{eqnarray*} A^1 \end{eqnarray*}$ und so fange ich bei der Induktion auch an, die annahme für i.ein beliebiges "einfaches" n zu beweisen?

In dem Fall setz ich einfach nur 1 ein und es müsste dann
$\begin{eqnarray*} A=\begin{pmatrix} 1&2 \\ 2&4 \end{pmatrix} \end{eqnarray*}$
rauskommen?

Rechnung:
$\begin{eqnarray*} A^1=\begin{pmatrix} 1\cdot 5^{1-1}&2\cdot 5^{1-1} \\ 2\cdot 5^{1-1}&4\cdot 5^{1-1} \end{pmatrix} = \begin{pmatrix} 1\cdot 1&2\cdot1 \\ 2\cdot 1&4\cdot1 \end{pmatrix} = \begin{pmatrix} 1&2 \\ 2&4 \end{pmatrix} \end{eqnarray*}$

somit hätte ich das bestätigt.

Da das aber für alle n gelten soll muss ich mal schauen obs für n+1 auch gillt in der Annahme das n schon bewiesen ist?
n+1 ist ja nichts anderes in dem Fall als $\begin{eqnarray*} A^n * A \end{eqnarray*}$

Dann kann ich einsetzen :
Hier hab ich dann n Fehler, verstehe nicht wie ihr auf das Ergebnis kommt.

$\begin{eqnarray*} A^{n+1} = \begin{pmatrix} 1\cdot 5^{n-1}&2\cdot 5^{n-1} \\ 2\cdot 5^{n-1}&4\cdot 5^{n-1} \end{pmatrix} \cdot \begin{pmatrix} 1&2 \\ 2&4 \end{pmatrix} \end{eqnarray*}$

warum ist das $\begin{eqnarray*} \begin{pmatrix} 5*5^{n-1} & 10*5^{n-1} \\ 10*5^{n-1} & 20*5^{n-1} \end{pmatrix} \end{eqnarray*}$

Grüße

13.02.2011, 19:52

Math1986

Auf diesen Beitrag antworten »

Bis zum folgenden Schritt ist alles richtig

Zitat:

Original von Broly
Dann kann ich einsetzen :
Hier hab ich dann n Fehler, verstehe nicht wie ihr auf das Ergebnis kommt.

$\begin{eqnarray*} A^{n+1} = \begin{pmatrix} 1\cdot 5^{n-1}&2\cdot 5^{n-1} \\ 2\cdot 5^{n-1}&4\cdot 5^{n-1} \end{pmatrix} \cdot \begin{pmatrix} 1&2 \\ 2&4 \end{pmatrix} \end{eqnarray*}$

warum ist das $\begin{eqnarray*} \begin{pmatrix} 5*5^{n-1} & 10*5^{n-1} \\ 10*5^{n-1} & 20*5^{n-1} \end{pmatrix} \end{eqnarray*}$

Multipliziere die Matrizen und fasse die einzelnen Einträge geschickt zusammen.. welcher Eintrag ist dir unklar?

13.02.2011, 20:58

Broly

Auf diesen Beitrag antworten »

Keine Ahnung , mich verwirrt das mit 5^n-1...

im normalfall würde ich ja normal so rechnen:

$\begin{eqnarray*} A^{n+1} = \begin{pmatrix} 1\cdot 5^{n-1}&2\cdot 5^{n-1} \\ 2\cdot 5^{n-1}&4\cdot 5^{n-1} \end{pmatrix} \cdot \begin{pmatrix} 1&2 \\ 2&4 \end{pmatrix}=\begin{pmatrix}5^{n-1}&2\cdot2\cdot 5^{n-1} \\2\cdot 2\cdot 5^{n-1}&4\cdot4\cdot 5^{n-1} \end{pmatrix}=\begin{pmatrix}5^{n-1}&4\cdot 5^{n-1} \\4\cdot 5^{n-1}&16\cdot 5^{n-1} \end{pmatrix} \end{eqnarray*}$

13.02.2011, 21:38

Math1986

Auf diesen Beitrag antworten »

Zitat:

Original von Broly
im normalfall würde ich ja normal so rechnen:

$\begin{eqnarray*} A^{n+1} = \begin{pmatrix} 1\cdot 5^{n-1}&2\cdot 5^{n-1} \\ 2\cdot 5^{n-1}&4\cdot 5^{n-1} \end{pmatrix} \cdot \begin{pmatrix} 1&2 \\ 2&4 \end{pmatrix}=\begin{pmatrix}5^{n-1}&2\cdot2\cdot 5^{n-1} \\2\cdot 2\cdot 5^{n-1}&4\cdot4\cdot 5^{n-1} \end{pmatrix}=\begin{pmatrix}5^{n-1}&4\cdot 5^{n-1} \\4\cdot 5^{n-1}&16\cdot 5^{n-1} \end{pmatrix} \end{eqnarray*}$

Dann solltest du dir die Matrizenmultiplikation nochmal ansehen unglücklich

unglücklich

"Zeile * Spalte"

13.02.2011, 22:48

Broly

Auf diesen Beitrag antworten »

Ah stimmt , macht Sinn:

$\begin{eqnarray*} A^{n+1} = \begin{pmatrix} 1\cdot 5^{n-1}&2\cdot 5^{n-1} \\ 2\cdot 5^{n-1}&4\cdot 5^{n-1} \end{pmatrix} \cdot \begin{pmatrix} 1&2 \\ 2&4 \end{pmatrix}=\begin{pmatrix}5^{n-1}+2\cdot2\cdot5^{n-1}&2\cdot5^{n-1}+4\cdot2\cdot 5^{n-1} \\ 2\cdot 5^{n-1}+2\cdot4\cdot5^{n-1}&2\cdot2\cdot5^{n-1}+4\cdot4\cdot 5^{n-1} \end{pmatrix}=\begin{pmatrix} 5\cdot 5^{n-1}&10\cdot 5^{n-1} \\ 10\cdot 5^{n-1}&20\cdot 5^{n-1} \end{pmatrix} \end{eqnarray*}$

nun ist mir auch klar das :
$\begin{eqnarray*} \begin{pmatrix} 5\cdot 5^{n-1}&10\cdot 5^{n-1} \\ 10\cdot 5^{n-1}&20\cdot 5^{n-1} \end{pmatrix}=\begin{pmatrix} 1\cdot 5^{n}&2\cdot 5^{n} \\ 2\cdot 5^{n}&4\cdot 5^{n} \end{pmatrix} \end{eqnarray*}$
ist. Zumindestens wenn ich Beispielsweise 1 einsetze^^

wie es jetzt aber weiter geht verstehe ich nicht ganz.

Grüße

13.02.2011, 22:51

Math1986

Auf diesen Beitrag antworten »

Zitat:

Original von Broly
nun ist mir auch klar das :
$\begin{eqnarray*} \begin{pmatrix} 5\cdot 5^{n-1}&10\cdot 5^{n-1} \\ 10\cdot 5^{n-1}&20\cdot 5^{n-1} \end{pmatrix}=\begin{pmatrix} 1\cdot 5^{n}&2\cdot 5^{n} \\ 2\cdot 5^{n}&4\cdot 5^{n} \end{pmatrix} \end{eqnarray*}$
ist.

Hier bist du fertig, genau das war im Induktionsschritt doch zu zeigen smile

smile

13.02.2011, 23:28

Broly

Auf diesen Beitrag antworten »

Dankeschön ;D Wink

Wink

Freude

Freude

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »