matematikk.net

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.

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
?

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$

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].

Løste den på samme måte!