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.
Fibonacci-tall
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
[tex]\gcd(F_{n}, F_{n+1})=1[/tex]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.
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]
Marie Curie, kjemiker og fysiker.
[tex]\large\dot \rho = -\frac{i}{\hbar}[H,\rho][/tex]
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].
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].