Induktionsbeweis für xn = (3^n − 1) / 2 wenn x0, x1 und xn+1 gegeben sind

Question

Aufgabe:

Sei x₀ = 0, x₁ = 1 und x_n+1 = 4x_n − 3x_n−1 für alle n ∈ N größer als 1. Beweisen Sie, dass x_n = (3ⁿ − 1) / 2

Problem/Ansatz:

Ich hänge an dieser Aufgabe und finde gar keinen Zugang. Ich weiß, dass ich den Induktionsbeweis nutzen muss. Mein bisheriges Vorgehen ist, dass ich am Induktionsanfang zeige, dass die Formel für x_n für x₀ und x₁ gilt. Aber wie muss ich weiter vorgehen?

Ich freue mich über einen Denkanstoß :) !!

Answer 1

Du kannst es auf zwei Arten machen.

(1.) Direkt

Setzte \( x_n = \lambda^n \) in die Rekursion ein und bestimme \( \lambda \) aus einer quadratischen Gleichung und benutze die Anfangswerte sowie das Superpositionsprinzip umd die genaue Lösung zu nestimmen.

(2.)

Induktion:

Der Anfang ist leicht \( x_0 = \frac{3^0-1}{2} = 0 \)

Dann der Schluss von \( n \) auf \( n+1 \)

$$ x_{n+1} = 4 x_n - 3 x_{n-1} $$ und setzte für \( x_n \) und \( x_{n-1} \) die Ausdrücke \( \frac{3^n-1}{2} \) bzw. \( \frac{3^{n-1}-1}{2} \) ein und rechne alles aus.

Comments

Danke @ullim. Ich habe mich für den 2. Weg entschieden. Dank deiner und mathef Antwort bin ich gut durch die Aufgabe gekommen.

Answer 2

dass ich am Induktionsanfang zeige, dass die Formel für xn für x0 und x1 gilt

Genau!

Und dann nimm an, sie gilt für alle Werte bis zu einem n.

Und zeige, dass sie auch für n+1 gilt. Also dass x_n+1 = (3^(n+1)  − 1) / 2 gilt.

Dazu fängst du so an:

x_n+1 =  4x_n − 3x_n−1 und für xn und xn-1 setzt du jetzt die Formeln ein:

   = 4*(  ( 3^n - 1  ) / 2 ) - 3*( 3^(n-1) - 1 )   / 2 )

     =  (4* 3^n    - 4 ) / 2      - ( 3^n  - 3)  / 2

=   (4* 3^n   - 4 )      - ( 3^n - 3)       )   / 2

=  (4* 3^n   - 4      -  3^n + 3)      / 2

=  (3* 3^n   - 1 )      / 2

=  ( 3^(n+1)    - 1 )      / 2    q.e.d.

Comments

super. Vielen Dank für den Ansatz! Damit konnte ich die Aufgabe gut zu Ende bringen :)