Homogene lineare Rekurrenzgleichungen zweiter Ordnung

Question

Die Homogene lineare Rekkurenzgleichungen zweiter Ordnung ist definiert als:

T(n) = a₁T(n − 1) + a₂T(n − 2) für n ≥ 2
T(1) = b₁
T(0) = b₀,

Beweisen Sie die  Lösung für homogene lineare Rekurrenzgleichungen zweiter Ordnung in den folgenden Schritten:

1)

Zeigen Sie die Korrektheit der angegebenen Lösung für T(0) und T(1). Beachten Sie dabei die beiden Fälle α = β und α ≠ β.

2)

Zeigen Sie, dass für α = β gilt: a₁ = 2α , a₂ = −α ². Beachten Sie, dass α und β reelle Lösungen der Gleichung t² − a₁ · t − a₂ = 0 sind.

3)

Zeigen Sie, dass für α ≠ β gilt: a₁ = α + β, a₂ = −αβ

4)

Rechnen Sie nach, dass T(n) = (A · n + B)αⁿ für α = β und n > 1 gilt.

5)

Zeigen Sie, dass T(n) = A · αⁿ − B · βⁿ für α ≠ β und n > 1 gilt.