0

Ich soll die Anzahl der Kreise der Länge 4 in einem Hyperwürfel mit der Dimension n zählen. Das sind ja alle Quadrate. 

Dafür habe ich erstmal alle Kanten gezählt: $n*2^{n-1}$ für n=Dimension und n≥1

Quadrate (Kreise der Länge 4) gibt es erst ab n=2. Für n=2 gibt es 1 Quadrat. Für n=3 gibt es 6, für n=4 gibt es 24, für n=5 gibt es 80.... usw. 
 
Genaugenommen kann man die Anzahl rekursiv berechnen mit Anzahl der Kanten + 2* Anzahl der Quadrate der Dimension davor. Also für n=3 ist gibt es 4 Kanten und einen Quadrat. Also gibt es in der 4. Dimension 4+2*1 = 6 Quadrate. 

Rekursionsvorschrift: $a_{n+1}$ = $n*2^{n-1}$ + $2*a_{n}$

Explizite Vorschrift für $a_{n}$ ist vermutlich $n(n+1)2^{n-2}$ (1, 6, 24, 80,...)
Induktionsanfang passt für n=2 ,3 ,4 ,5

Wenn ich jetzt im Induktionsschritt $a_{n}$ (explizite Vorschrift) in $a_{n+1}$  (Rekursionsvorschrift) einsetze kommt am Ende $a_{n+1}$ = $2^{n-1}$ $n(n+2)$ heraus. Aber leider nicht $a_{n+1}$ = $2^{n-1}$ $(n+1)(n+2)$ , was ja eigentlich das Ziel ist. 

Wo liegt mein Fehler, sieht es jemand?

Danke im Voraus!

Diese Frage melden
gefragt

Punkte: 22

 
Kommentar schreiben
1 Antwort
0
Immer sorgfältig beim Induktionsanfang, der passt nämlich mit Deiner Formel nicht (da wäre z.B. $a_2=6$). Da ist alles um 1 verschoben, die richtige explizite Formel lautet:
$a_n=n\,(n-1)\,2^{n-3}$. Damit passt der Induktionsanfang und auch der Induktionsschritt.
Diese Antwort melden
geantwortet

Lehrer/Professor, Punkte: 26.7K

 

Ich komme irgendwie nicht auf die Form $a_{n+1}$ = $(n+1)(n+2)2^{n-1}$
Ich habe $a_{n}$ = $n(n-1)2^{n-3}$ in meine Rekursionsformel $a_{n+1}$ = $n2^{n-1}+2a_{n}$ eingesetzt und es geht irgendwie nicht auf.
Wenn ich alles ausmultipilziere bekomme ich $2^{n-1}(n+\frac{n^2-n}{2})$ was ja offensichtlich nicht mein ursprüngliches Ziel in meinem Induktionsbeweis ist : $(n+1)(n+2)2^{n-1}$
Was mache ich falsch?
  ─   huhu123 17.06.2022 um 16:52

Dein a_n+1, das Ziel, stimmt nicht. Setze richtig ein.   ─   mikn 17.06.2022 um 17:16

Danke!
  ─   huhu123 17.06.2022 um 17:48

Kommentar schreiben