quadr. Matrix ^n Beweis < Matrizen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Berechne für n [mm] \in \IN
[/mm]
[mm] \pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 }^{n} [/mm] |
Hallo MatheRaum Community,
ich hab mich dran versucht diese Aufgabe mittels vollst. Induktion zu lösen/beweisen, aber komme beim Ind.-Schluss nicht mehr weiter.
Also mittels einigem Ausprobieren habe ich diese(s) "Muster"/Regel erkannt.
[mm] \pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1}^{n} [/mm] = [mm] \pmat{ 1 & n & n+c_{1(n-1)} \\ 0 & 1 & n \\ 0 & 0 & 1}
[/mm]
das Element [mm] c_{1(n-1)} [/mm] wäre dann das Element was für n-1 an dieser Stelle stehen würde.
Also nun zur Induktion:
Induktions-Anfang : für n = 1
[mm] \pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1}^{1} [/mm] = [mm] \pmat{ 1 & 1 & 1+c_{1(n-1)} \\ 0 & 1 & 1 \\ 0 & 0 & 1} [/mm]
und das [mm] c_{1(n-1)} [/mm] wäre bei n=1, das Element was bei n=0, also: [mm] \pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1}^{0} [/mm] an dieser Stelle stehen würde, was 0 wäre.
Also:
[mm] \pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1}^{1} [/mm] = [mm] \pmat{ 1 & 1 & 1+0 \\ 0 & 1 & 1 \\ 0 & 0 & 1} [/mm]
Hierbei bitte ich auch kurz um eine Erklärung warum da 0 stehen müsste für [mm] c_{1(n-1)} [/mm] . Im Internet habe ich ein bisschen recherchiert und die Cayley Hamilton Regel müsste das irgendwie erklären können, da diese Matrix quadratisch ist, aber mehr habe ich nicht verstehen können, da dies die 1. Woche mit Matrizenrechnung bei mir ist.
Induktions-Vorausetzung :
[mm] \pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1}^{n} [/mm] = [mm] \pmat{ 1 & n & n+c_{1(n-1)} \\ 0 & 1 & n \\ 0 & 0 & 1} [/mm]
Induktions-Behauptung :
[mm] \pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1}^{n+1} [/mm] = [mm] \pmat{ 1 & n+1 & n+1+n+c_{1(n-1)} \\ 0 & 1 & n+1 \\ 0 & 0 & 1} [/mm]
Induktions-Schluss :
[mm] \pmat{ 1 & n+1 & n+1+n+c_{1(n-1)} \\ 0 & 1 & n+1 \\ 0 & 0 & 1} [/mm] = [mm] \pmat{ 1 & n & n+c_{1(n-1)} \\ 0 & 1 & n \\ 0 & 0 & 1} [/mm] + [mm] \pmat{ 0 & 1 & n+1 \\ 0 & 0 & 1 \\ 0 & 0 & 0} [/mm]
Der erste Teil wäre ja die Induktions-Voraussetzung aber wie genau kann ich denn jetzt zeigen, dass es das selbe ist?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Ich danke schonmal im Voraus.
Mit freundlichen Grüßen,
Cifer
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:41 Sa 05.12.2015 | | Autor: | hippias |
> Berechne für n [mm]\in \IN[/mm]
>
> [mm]\pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 }^{n}[/mm]
> Hallo
> MatheRaum Community,
> ich hab mich dran versucht diese Aufgabe mittels vollst.
> Induktion zu lösen/beweisen, aber komme beim Ind.-Schluss
> nicht mehr weiter.
>
> Also mittels einigem Ausprobieren habe ich diese(s)
> "Muster"/Regel erkannt.
>
> [mm]\pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1}^{n}[/mm] = [mm]\pmat{ 1 & n & n+c_{1(n-1)} \\ 0 & 1 & n \\ 0 & 0 & 1}[/mm]
>
> das Element [mm]c_{1(n-1)}[/mm] wäre dann das Element was für n-1
> an dieser Stelle stehen würde.
>
> Also nun zur Induktion:
>
> Induktions-Anfang : für n = 1
> [mm]\pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1}^{1}[/mm] = [mm]\pmat{ 1 & 1 & 1+c_{1(n-1)} \\ 0 & 1 & 1 \\ 0 & 0 & 1}[/mm]
>
> und das [mm]c_{1(n-1)}[/mm] wäre bei n=1, das Element was bei n=0,
> also: [mm]\pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1}^{0}[/mm] an
> dieser Stelle stehen würde, was 0 wäre.
>
> Also:
> [mm]\pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1}^{1}[/mm] = [mm]\pmat{ 1 & 1 & 1+0 \\ 0 & 1 & 1 \\ 0 & 0 & 1}[/mm]
>
> Hierbei bitte ich auch kurz um eine Erklärung warum da 0
> stehen müsste für [mm]c_{1(n-1)}[/mm] .
Ich bin mir nicht sicher, ob ich Deine Frage richtig verstehe. Meine Antwort ist, dass eine Matrix hoch $0$ nach Definition die Einheitsmatrix ist. Daher ist der betreffende Matrixeintrag $=0$.
> Im Internet habe ich ein
> bisschen recherchiert und die Cayley Hamilton Regel müsste
> das irgendwie erklären können, da diese Matrix
> quadratisch ist, aber mehr habe ich nicht verstehen
> können, da dies die 1. Woche mit Matrizenrechnung bei mir
> ist.
>
> Induktions-Vorausetzung :
>
> [mm]\pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1}^{n}[/mm] = [mm]\pmat{ 1 & n & n+c_{1(n-1)} \\ 0 & 1 & n \\ 0 & 0 & 1}[/mm]
>
> Induktions-Behauptung :
>
> [mm]\pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1}^{n+1}[/mm] = [mm]\pmat{ 1 & n+1 & n+1+n+c_{1(n-1)} \\ 0 & 1 & n+1 \\ 0 & 0 & 1}[/mm]
>
Nein, oben rechts müsste, in Deiner etwas wunderlichen Notation, [mm] $n+1+c_{1n}$ [/mm] stehen, da Du den Vorgängerfall zu $n+1$ benötigst.
> Induktions-Schluss :
> [mm]\pmat{ 1 & n+1 & n+1+n+c_{1(n-1)} \\ 0 & 1 & n+1 \\ 0 & 0 & 1}[/mm]
> = [mm]\pmat{ 1 & n & n+c_{1(n-1)} \\ 0 & 1 & n \\ 0 & 0 & 1}[/mm]
> + [mm]\pmat{ 0 & 1 & n+1 \\ 0 & 0 & 1 \\ 0 & 0 & 0}[/mm]
>
Nein, rechne so: [mm] $\pmat{1 & 1 & 1\\ 0&1&1\\ 0&0&1}^{n+1}= \pmat{1 & 1 & 1\\ 0&1&1\\ 0&0&1}^{n}\pmat{1 & 1 & 1\\ 0&1&1\\ 0&0&1}$. [/mm] Nach Induktionsvoraussetzung ist [mm] $\pmat{1 & 1 & 1\\ 0&1&1\\ 0&0&1}^{n}= \pmat{1 & n & n+c_{1(n-1)}\\ 0&1&n\\ 0&0&1}$.
[/mm]
Also ist [mm] $\pmat{1 & 1 & 1\\ 0&1&1\\ 0&0&1}^{n+1}= \pmat{1 & n &n+ c_{1(n-1)}\\ 0&1&n\\ 0&0& 1}\pmat{1 & 1 & 1\\ 0&1&1\\ 0&0&1}$. [/mm] Nun berechne das Matrixprodukt auf der rechten Seite, insbesondere den Eintrag in der rechten oberen Ecke und überprüfe, ob er die richtige Gestalt hat.
Ich würde versuchen einen expliziten Ausdruck für das [mm] $c_{1n}$ [/mm] zu finden (Tip: Arithmetische Reihe).
> Der erste Teil wäre ja die Induktions-Voraussetzung aber
> wie genau kann ich denn jetzt zeigen, dass es das selbe
> ist?
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
>
> Ich danke schonmal im Voraus.
>
> Mit freundlichen Grüßen,
> Cifer
|
|
|
| |
|
Erst einmal vielen Dank für die Hilfe und den hilfreichen Tipp mit der arithmetischen Reihe. Perfekt dezenter Tipp kann ich nur sagen.
Also ich hab das nochmal versucht in dem ich für [mm] c_{1(n-1)} [/mm] die Gaußsche Summenformel eingesetzt habe also [mm] \bruch{n(n+1)}{2} [/mm] und dann würde mein Induktionsbeweis so aussehen:
Induktionsanfang: für n=1
[mm] \pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1}^{1} [/mm] = [mm] \pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1} [/mm]
Induktionsvoraussetzung:
[mm] \pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1}^{n} [/mm] = [mm] \pmat{ 1 & n & \bruch{n(n+1)}{2} \\ 0 & 1 & n \\ 0 & 0 & 1} [/mm]
Induktionsbehauptung:
[mm] \pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1}^{n+1} [/mm] = [mm] \pmat{ 1 & n+1 & \bruch{(n+1)(n+2)}{2} \\ 0 & 1 & n+1 \\ 0 & 0 & 1} [/mm]
Induktionsschluss:
[mm] \pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1}^{n+1} [/mm] = [mm] \pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1}^{n} [/mm] * [mm] \pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1} [/mm] = [mm] \pmat{ 1 & n & \bruch{n(n+1)}{2} \\ 0 & 1 & n \\ 0 & 0 & 1} [/mm] * [mm] \pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1} [/mm] = [mm] \pmat{ 1 & n+1 & \bruch{(n+1)(n+2)}{2} \\ 0 & 1 & n+1 \\ 0 & 0 & 1} [/mm]
Nebenrechnung zum Induktionsschluss:
n+1+ [mm] \bruch{n(n+1)}{2} [/mm] = [mm] \bruch{2n}{2} [/mm] + [mm] \bruch{2}{2} [/mm] + [mm] \bruch{n(n+1)}{2} [/mm] = [mm] \bruch{2n+2+n^2+n}{2} [/mm] = [mm] \bruch{3n+n^2+2}{2} [/mm] = [mm] \bruch{(n+1)(n+2)}{2}
[/mm]
Eine Frage hätte ich noch und zwar bei dem Schritt wo ich [mm] 3n+n^2+2 [/mm] = (n+1)(n+2) gesetzt habe: Also diesmal habe ich das halt erkannt weil ich mir schon früher aufgeschrieben hatte, dass (n+1)(n+2) im Zähler stehen muss und ich es mal einfach so ausgeklammert hatte um zu gucken was dabei rauskommt. Ich wusste also schon im voraus, dass irgendwie entweder [mm] 3n+n^2+2 [/mm] oder (n+1)(n+2) im Zähler stehen muss, aber gibt es da irgendwie einen Trick sowas zu erkennen. Der erste Gedanke war bei mir nämlich als ich [mm] 3n+n^2+2 [/mm] rausbekommen hatte im Zähler, dass ich mich vielleicht irgendwo vertan habe, weil ich nicht (n+1)(n+2) rausbekommen habe und erst beim Überlegen mein Blick über das Blatt schweifte und ich sah, dass (n+1)(n+2) = [mm] 3n+n^2+2 [/mm] ist. Hätte ich das irgendwie früher erkennen können? Eine binomische Formel ist das ja nicht wirklich und wenn ich versuche n auszuklammern kommt bei mir ja n(n+3)+2 raus, welches auf den ersten Blick auch nicht so aussieht wie (n+1)(n+2).
Und dann natürlich noch die Frage ob der Beweis nun beendet ist oder ob da noch was fehlt.
Vielen Dank noch einmal.
Mit freundlichen Grüßen,
Baran Calisci
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:49 So 06.12.2015 | | Autor: | hippias |
Ich finde Dein Beweis sieht gut so aus. Zu Deiner Frage: Ich schätze, jeder findet es nicht leicht die Gleichheit der Terme zu erkennen; insbesondere, wenn mehr als $2$ Faktoren involviert sind. Da hilft nur Klammern auszumultiplizieren, um zu sehen, ob die Terme gleich oder ungleich sind.
Ich möchte aber an den Satz von Vieta erinnern, der einem z.B. bei $2$ Faktoren schnell erkennen lässt wie die Faktoren vor den Potenzen aussehen.
Richie1401s Idee mit der binomischen Formel ist natürlich sehr elegant. Wenn ich keine Fehler oder unnötig sehr viel Mehraufwand sehe, dann halte ich mich mit Alternativbeweisen meist zurück, damit der Lernende seine eigenen Ideen entwickeln kann.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:26 So 06.12.2015 | | Autor: | DieAcht |
Hallo Ulquiorra!
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
> Eine Frage hätte ich noch und zwar bei dem Schritt wo ich
> [mm]3n+n^2+2[/mm] = (n+1)(n+2) gesetzt habe: Also diesmal habe ich
> das halt erkannt weil ich mir schon früher aufgeschrieben
> hatte, dass (n+1)(n+2) im Zähler stehen muss und ich es
> mal einfach so ausgeklammert hatte um zu gucken was dabei
> rauskommt. Ich wusste also schon im voraus, dass irgendwie
> entweder [mm]3n+n^2+2[/mm] oder (n+1)(n+2) im Zähler stehen muss,
> aber gibt es da irgendwie einen Trick sowas zu erkennen.
Das Aufschreiben der Induktionsbehauptung ist bereits ein "Trick", weil man damit das "Ziel" im Blick behält.
> Der erste Gedanke war bei mir nämlich als ich [mm]3n+n^2+2[/mm]
> rausbekommen hatte im Zähler, dass ich mich vielleicht
> irgendwo vertan habe, weil ich nicht (n+1)(n+2)
> rausbekommen habe und erst beim Überlegen mein Blick über
> das Blatt schweifte und ich sah, dass (n+1)(n+2) = [mm]3n+n^2+2[/mm]
> ist. Hätte ich das irgendwie früher erkennen können?
> Eine binomische Formel ist das ja nicht wirklich und wenn
> ich versuche n auszuklammern kommt bei mir ja n(n+3)+2
> raus, welches auf den ersten Blick auch nicht so aussieht
> wie (n+1)(n+2).
In der Regel ist bei solchen Aufgaben das Ausmultiplizieren das falsche Mittel.
Es gilt
[mm] $n+1+\frac{n*(n+1)}{2}=\frac{2*(n+1)}{2}+\frac{n*(n+1)}{2}=\frac{2*(n+1)+n*(n+1)}{2}=\frac{(n+1)(n+2)}{2}$.
[/mm]
Gruß
DieAcht
|
|
|
| |
|
Hallo,
es geht auch einfacher:
Ich nehme an, dass ihr den Binomischen Lehrsatz hattet, sodass ihr ihn verwenden dürft.
Zerlege deine Matrix wie folgt
[mm] \pmat{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 }=\pmat{ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 }+\pmat{ 0 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 0 }=E_3+B
[/mm]
Nutze nun den Binomischen Lehrsatz (das ist möglich da die Identische Matrix natürlich mit der Matrix B kommutiert):
[mm] (E_3+B)^n=\sum_{k=0}^n\binom{n}{k}{E_3}^{n-k}B^k=\sum_{k=0}^{2}\binom{n}{k}B^k
[/mm]
Die Summe geht natürlich nur bis n=2, da [mm] B^3=0.
[/mm]
Die "Arbeit" liegt jetzt nur noch darin, die Binomialkoeffizienten zu berechnen und die drei Matrizen (wobei sicherlich bekannt ist, welche Gestalt [mm] B^2 [/mm] hat) aufzusummieren.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:05 Sa 05.12.2015 | | Autor: | Ulquiorra |
Tut mir leid, aber ich hab gar nicht erst versucht es mit dem Binomialkoeffizienten zu lösen, da ich es mit hippias Tipp schon geschafft hatte, sonst hätte ich es so versucht, wie du es mir angeboten hattest. Trotzdem echt vielen Dank für die Hilfe und nimm es mir nicht übel, dass ich es nicht damit versucht habe.
Mit freundlichen Grüßen,
Cifer
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:59 Sa 05.12.2015 | | Autor: | Richie1401 |
Hallo,
ich nehme dir das überhaupt nicht übel. Ich wollte jedoch nur für andere - die vielleicht auf diese Aufgabe stoßen - einen alternativen Lösungsweg anbieten.
Zumal dieser Lösungsweg eigentlich nur ein Dreizeiler ist. Denn rechnen muss man hier eigentlich gar nicht.
Übrigens ist ja in der Tat nur ein einziger Binomialkoeffizient zu "berechnen".
Also schneller geht es glaube ich wirklich nicht.
Als Übung für die Beweistechnik der Induktion ist obige Aufgabe aber sicherlich nicht schlecht.
Es kann ja allgemein nie schaden sich mehrere Lösungen anzuschauen.
|
|
|
|
