Fibonacci-tall

Her kan brukere av forum utfordre hverandre med morsomme oppgaver og nøtter man ønsker å dele med andre. Dette er altså ikke et sted for desperate skrik om hjelp, de kan man poste i de andre forumene, men et sted for problemløsing på tvers av trinn og fag.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Svar
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

Fibonacci-tallene er definert rekursivt ved at $F_1=F_2=1$ og $F_n=F_{n-1}+F_{n-2}$.

Vis at to påfølgende Fibonacci-tall er relativt primiske.
Janhaa
Boltzmann
Boltzmann
Innlegg: 8552
Registrert: 21/08-2006 03:46
Sted: Grenland

plutarco skrev:Fibonacci-tallene er definert rekursivt ved at $F_1=F_2=1$ og $F_n=F_{n-1}+F_{n-2}$.
Vis at to påfølgende Fibonacci-tall er relativt primiske.
[tex]\gcd(F_{n}, F_{n+1})=1[/tex]

eller evt induksjon
?
La verken mennesker eller hendelser ta livsmotet fra deg.
Marie Curie, kjemiker og fysiker.

[tex]\large\dot \rho = -\frac{i}{\hbar}[H,\rho][/tex]
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

Jau, det er dette du da skal vise. Har du et bevis?

Hint:
[+] Skjult tekst
Bevis ved motsigelse: Anta at det fins et naturlig tall $d>1$ som deler $F_{n-1}$ og $F_n$
Emilga
Riemann
Riemann
Innlegg: 1552
Registrert: 20/12-2006 19:21
Sted: NTNU

Jeg benytter meg av hintet.

Anta [tex]\exists \; d > 1[/tex] slik at [tex]F_{n} = d\cdot a[/tex] og [tex]F_{n-1} = d\cdot b[/tex] for naturlige tall [tex]a[/tex] og [tex]b[/tex].

Har da at [tex]F_{n-2} = F_n - F_{n-1} = d\cdot a - d\cdot b = d\cdot (a-b)[/tex], altså må [tex]d[/tex] også være en divisor til det forrige Fibonacci-tallet.

Dette fortsetter helt til [tex]F_1 = d\cdot (\ldots ) = 1[/tex].

Her har vi en selvmotsigelse, altså må [tex]d=1[/tex].
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

Løste den på samme måte!
Svar