Induktion: Matrizen potenzieren. Formel für ((1,1,0),(0,1,1),(0,0,1))^n

Question

die Aufgabe besteht darin durch probieren Formeln für die Einträge der Matrizen zu finden in Abhängigkeit von n Element aller natürlichen Zahlen und die Richtigkeit anschließend durch Induktion zu beweisen.

Wäre über Hilfe sehr erfreut, kann nämlich die einzelnen Rechenschritte nicht wirklich nachvollziehen. Alternative Lösungen sind auch in Ordnung :)

Das war eine Aufgabe/Lösung aus einer Übungsseminar in Mathe

Comments

Tipp: die Summe in der oberen Ecke lässt sich nach Gauß zu

sum(k=0 bis n-1) k =1/2(n-1)*n

berechnen. Der Eintrag oben im der Mitte muss wohl n lauten, oder?

---

Hallo nury,

In der ersten Zeile ist schon ein Fehler. Da fehlt ein \(n\):

$$\begin{pmatrix}1& 1& 0\\ 0& 1& 1\\ 0& 0& 1\end{pmatrix}^n = \begin{pmatrix}1& \colorbox{#FFFF00}{n}& \sum_{k=0}^{n-1}k\\ 0& 1& n\\ 0& 0& 1\end{pmatrix}$$

Ah - in der dritten Zeile taucht es wieder auf. Wo genau ist denn Dein Problem? Steht doch alles da!

---

mien Problem ist, dass ich nicht nachvollziehen kann wie die einzelnen schritte zustande kommen. welche Regeln, formeln etc angewendet werden

---

Zur Lösung der Aufgabe benötigst du Wissen zu:

- vollständiger Induktion

- Matrizenmultiplikation

- Addition und Multiplikation von reellen Zahlen

---

Hallo nury,

jetzt hätte ich Deine Rückfrage fast noch vergessen:

mein Problem ist, dass ich nicht nachvollziehen kann wie die einzelnen Schritte zustande kommen. Welche Regeln, Formeln etc angewendet werden?

Was genau ist Dein Problem? Ist es eher der Beweis mittels vollständiger Induktion oder die Multiplikation von Matrizen? Oder etwas anderes?

Gruß Werner

Answer 1

Du kannst die Matrix schreiben als

$$  A = \begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix} = I + N $$
Die Matrix \( N \) ist nilpotent und es gilt \( N^3 = 0 \) und \( I N = N I \)
Damit gilt die binomische Formel mit
$$ (I + N)^n = \sum_{i=0}^n \binom{n}{i} I^{n-i} N^i = \sum_{i=0}^2 \binom{n}{i} N^i = I + nN + \frac{n(n-1)}{2}N^2  $$ und das entspricht dem, was Du beweisen sollst

Comments

Hallo ullim,

... das ist zwar nicht die Antwort auf die Frage, aber die Antwort ist zu gut, um sie von der 'falschen' Frage verderben zu lassen. Daher ein Däumchen von mir.

Gruß Werner

---

Ok, ist ein alternativer Weg, um zur Lösung zu kommen. Man kann ja auch mal einen anderen, als vorgegebenen Weg, gehen.