Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » eine Fibonacci Folge mit Modulo

eine Fibonacci Folge mit Modulo

Universität / Fachhochschule

Tags: Beweis durch vollständig Induktion, Fibonacci Folge, Induktion, modulo

Khalil7 aktiv_icon

17:26 Uhr, 24.06.2020

Hallo Leute ;
wie geht es mit dieser Aufgabe
Die Fibonacci-Folge ist gegeben durch

F (0) = 1, F (1) = 1, \forall n > 1 (F (n) = F (n

−

1) + F (n

−

2))

Beweise Sie durch Induktion:

F (n)

gerade ⇐⇒

n

≡

2 mod 3

HAL9000

19:42 Uhr, 24.06.2020

Induktionsanfang: Überprüfe die Behauptung für

n = 1

UND

n = 2

.

Für alle

n \geq 3

der Induktionsschritt

(< n) \to n

:

Betrachte getrennt die drei Fälle

n \equiv 0, 1, 2 mod 3

und nutze dabei jeweils die Induktionsvoraussetzung für

n - 1

und

n - 2

via

F (n) = F (n - 1) + F (n - 2)

.

-----------------------------------------

Für die originale Fibonaccifolge mit "richtigem" Index, d.h.

f_{n} = F (n - 1)

gilt übrigens die viel viel mächtigere
Aussage

ggT (f_{n}, f_{m}) = f_{ggT (n, m)}

. Spezialfall

m = 3

mit

f_{3} = 2

ergibt da

ggT (f_{n}, 2) = f_{ggT (n, 3)}

d.h.

2 ∣ f_{n}

genau dann wenn

3 ∣ n

, das entspricht der obigen Behauptung.

anonymous

02:22 Uhr, 25.06.2020

Hallo,

eine kurze Antwort ohne großen Rummel:

OBdA repräsentiere

u

jede natürliche Zahl

n,

für die

n mod 2 = 1

gilt und

g

jede natürliche Zahl

n,

für die

n mod 2 = 0

gilt.

Gilt für ein

n \in N_{> 1}

F (n - 2) = F (n - 1) = u,

so folgt daraus

F (n) = g, F (n + 1) = u, F (n + 2) = u

und somit induktiv

F (n + k \cdot 3) = g, F (n + 1 + k \cdot 3) = u, F (n + 2 + k \cdot 3) = u \forall k \in N

.
Mit

F (0) = F (1) = 1

folgt die Behauptung.

Und "just for fun" eine kurze Herleitung
der stetigen Funktion zur Folge nach Backrezept:

F (n) - F (n - 1) - F (n - 2) = 0

\to

x^{2} - x - 1 = 0

{(x - \frac{1}{2})}^{2} = \frac{5}{4}

x = \pm \frac{\sqrt{5}}{2} + \frac{1}{2}

\to

k_{1} + k_{2} = 1

k_{1} \cdot (\frac{\sqrt{5}}{2} + \frac{1}{2}) + k_{2} \cdot (- \frac{\sqrt{5}}{2} + \frac{1}{2}) = 1

k_{1} \cdot (\frac{\sqrt{5}}{2} + \frac{1}{2} + \frac{\sqrt{5}}{2} - \frac{1}{2}) = \frac{\sqrt{5}}{2} + \frac{1}{2}

k_{1} = \frac{\sqrt{5} + 1}{2 \cdot \sqrt{5}}

k_{2} = \frac{\sqrt{5} - 1}{2 \cdot \sqrt{5}}

\to

F (x) = \frac{1}{\sqrt{5}} \cdot ({(\frac{1 + \sqrt{5}}{2})}^{x + 1} - {(\frac{1 - \sqrt{5}}{2})}^{x + 1})

HAL9000

07:06 Uhr, 25.06.2020

Das nennst du "ohne großen Rummel" ? Mal so eben Binet herleiten, welcher für die vorliegende Behauptung gar nichts bringt? :-D)

anonymous

07:26 Uhr, 25.06.2020

Na ja, die Aufgabe ist ja nun bis auf die Formalitäten erschlagen.
Äh, "Binet" ist diese Funktion, oder was ?

HAL9000

08:57 Uhr, 25.06.2020

Ja: de.wikipedia.org/wiki/Fibonacci-Folge#Formel_von_Moivre-Binet

ermanus aktiv_icon

09:27 Uhr, 25.06.2020

Hallo,
ich mache mir immer gern ein "anschauliches Bild" der Verhältnisse.
Rechnen wir die Werte der Fibonacci-Folge modulo 2, so bekommen wir
1 1 0 1 1 0 1 1 0 ... ,
da je zwei benachbarte Werte summiert den Folgewert ergeben.
Gruß ermanus

1507653

1507591

	Status: nicht eingeloggt	Noch nicht registriert?