Wie berechnet man die Lukaszahlen?

Question

Die Lukaszahlen sind durch folgende Rekurrenzgleichung definiert.

L0 = 2
L1 = 1
Ln = Ln−1 + Ln−2 für n ≥ 2

(a) Zeigen Sie, dass Ln = Fn−1 + Fn+1 für n ≥ 1 gilt, wobei Fn die Fibonaccizahlen sind.
(b) Geben Sie für Ln eine explizite Darstellung an

 

Ich muss gestehen, dass ich hier komplett auf dem Schlauch stehe, da Mathe so gar nicht meine Stärke ist und wir die Aufgabe in Informatik gestellt bekommen haben.

Answer 1

Das es für n = 1, 2 gilt ist offensichtlich. Daher müssen wir nur zeigen, dass es für n+2 gilt, unter der annahme das es für n  und n+1 gilt.

Ln+2 = Ln + Ln+1 = Fn-1 + Fn+1 + Fn + Fn+2 = (Fn-1 + Fn) + (Fn+1 + Fn+2)  = Fn+1 + Fn+3

Das war zu beweisen also stimmt es.

Dürft ihr bei b) die Formel von Moivre-Binet voraussetzen?

Dann gilt:

Ln = ((1 + √5)/2)^n + ((1 - √5)/2)^n