Fibonacci-Zahlen-Lösung für diese Wiederholungsbeziehung

Question

TAPLON

Beweisen Sie, dass die Fibonacci-Zahlen die Lösungen der folgenden Wiederholungsrelation sind,

S_{N} = 5 S_{N - 4} + 3 S_{N - 5}

$S_n=5S_{n-4}+3S_{n-5}$ Für alle n größer oder gleich 5, wo wir haben

S_{0} = 0

$S_0=0$

S_{1} = 1

$S_1=1$

S_{2} = 1

$S_2=1$

S_{3} = 2

$S_3=2$

S_{4} = 3

$S_4=3$ Verwenden Sie dann die Formel, um zu zeigen, dass die Fibonacci-Zahlen die Bedingung erfüllen, dass

f_{n}

$f_n$ ist genau dann durch 5 teilbar, wenn n durch 5 teilbar ist.

Der erste Teil ist ein äußerst einfacher Induktionsbeweis. Zeigen Sie zum zweiten, dass die Rekursion dies impliziert

S_{n} \equiv S_{n - 5} (\mod 5)

$S_n\equiv S_{n-5}\pmod5$ .

Der erste Teil ist ein äußerst einfacher Induktionsbeweis. Zeigen Sie zum zweiten, dass die Rekursion dies impliziert $S_n\equiv S_{n-5}\pmod5$ .

Chosrotasch · Answer 1

Hinweis: charakteristische Gleichung

X^{5} = 5 X + 3 X^{5} - 5 X - 3 = 0

$x^5=5x+3\\x^5-5x-3=0$ Dann

X^{2} - X - 1 | X^{5} - 5 X - 3 \to

$x^2-x-1|x^5-5x-3\\ \to$ teilen

x^{5} - 5 x - 3

$x^5-5x-3$ von

x^{2} - x - 1

$x^2-x-1$

X^{5} - 5 X - 3 = (X^{2} - X - 1) (X^{3} + X^{2} + 2 X + 3)

$x^5-5x-3=(x^2-x-1)(x^3+x^2+2x+3)$ Und

x^{2} - x - 1

$x^2-x-1$ ist die charakteristische Gleichung von

f_{n} = f_{n - 1} + f_{n - 2} - - - -

$f_n=f_{n-1}+f_{n-2}\\----\\$

Noch eine Lösung:

F_{N + 5} = F_{N + 4} + F_{N + 3} = (F_{N + 3} + F_{N + 2}) + F_{N + 3} = 2 F_{N + 3} + F_{N + 2}

$f_{n+5}=f_{n+4}+f_{n+3}\\ =(f_{n+3}+f_{n+2})+f_{n+3}=\\2f_{n+3}+f_{n+2}$ jetzt setzen

f_{n + 3}

$f_{n+3}$

F_{N + 5} = 2 F_{N + 3} + F_{N + 2} = 2 (F_{N + 2} + F_{N + 1}) + F_{N + 2} = 3 F_{N + 2} + 2 F_{N + 1}

$f_{n+5}=2f_{n+3}+f_{n+2}=\\2(f_{n+2}+f_{n+1})+f_{n+2}=\\3f_{n+2}+2f_{n+1}\\$ und nun

F_{N + 5} = 3 F_{N + 2} + 2 F_{N + 1} = 3 (F_{N + 1} + F_{N}) + 2 F_{N + 1} = 5 F_{N + 1} + 3 F_{N}

$f_{n+5}=3f_{n+2}+2f_{n+1}=\\3(f_{n+1}+f_{n})+2f_{n+1}=\\5f_{n+1}+3f_n$