Side 1 av 1
Fibonacci-tall
Lagt inn: 15/09-2017 01:32
av Gustav
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.
Re: Fibonacci-tall
Lagt inn: 15/09-2017 13:07
av Janhaa
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
?
Re: Fibonacci-tall
Lagt inn: 15/09-2017 19:15
av Gustav
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$
Re: Fibonacci-tall
Lagt inn: 20/09-2017 09:52
av Emilga
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].
Re: Fibonacci-tall
Lagt inn: 21/09-2017 23:50
av Gustav
Løste den på samme måte!