Talföljden.. visa att ... är relativt prima.

Jag ska lösa uppgiften: Talföljden $f_{n}$ defineras enligt följande rekursion: $f_{0}$ =0, $f_{1}$ =1, $f_{n}$ = $f_{n - 1} + f_{n - 2}$ för n>1 Visa att Fn och Fn+1 är relativt prima.

Jag har tidigare löst en uppgifter med talföljder men då har det varit "visa med hjälp av induktion". Nu är det att visa att Fn och Fn+1 är relativt prima, så lite annorlunda.

Jag tänker att jag måste börja med att räkna ut Fn och Fn+1 och eftersom n<1 så måste jag fortsätta i talföljden:

Fn= 1+0= 1

Fn+1= 1+1= 2

Fn+2 (F5) = 2+1 =3

Fn+3 (F6) = 3+2 =5

Fn+4 (F7) = 5+3=8 Här är det inte ett relativt prima tal?

Sedan ska visa att dom är relativt prima, dvs att deras största gemensamma delare är 1. Hur kan jag bevisa detta på bästa sätt? Känns som jag har gjort något fel i talföljden eftersom F7 blev 8?

Tack på förhand!

Hej, det står att fn och f_n+1 är relativt prim. Det verkar också vara fibbonacis talföljd. Du kan prova ett motsägelsebevis. GCD( $F_0,F_1$ )=1 vilket tyder att de är relativa prima.Antag nu att F_n och F_n+1 hade någon gemensam faktor d>1...

Kommer du vidare? Du behöver endast visa att det inte kan finnas ett d>1 eftersom det då säger emot att GCD(F_0,F_1)=1.

Hej, jag vet inte riktigt hur jag ska göra med denna uppgift fortfarande faktiskt...

Ett induktionsbevis ska innehålla bevis för följande påståenden.

(1) $\text{gcd}(F_{0},F_{1}) = 1$

(2) Om $\text{gcd}(F_{n},F_{n+1}) = 1$ för något $n \geq 0$ så medför detta även att $\text{gcd}(F_{n+1},F_{n+2}) = 1$

För att visa (2) så kan det vara till hjälp att notera att $\text{gcd}(F_{n+1},F_{n+2}) = \text{gcd}(F_{n+1},F_{n} + F_{n+1}) = \text{gcd}(F_{n+1},F_{n})$ .

Snyggt Freewheeling, det är nog lättare än det jag hade i åtanke.

Min tanke var att man kunde gå denna vägen:

antag att $F_{k}$ och $F_{k + 1}$ hade en gemensam faktor d>1. per definition av fibbonacis talföljd så är $F_{k + 1} = F_{k} + F_{k - 1}$ så $F_{k - 1} = F_{k + 1} - F_{k}$ och eftersom d delar både $F_{k}$ och $F_{k + 1}$ måste det också dela $F_{k - 1}$ .... osv.

Jag förstår, det ser ju ut att funka bra om man innan gjort induktionsantagandet att $F_{k-1}$ och $F_{k}$ inte har en gemensam faktor som är större än 1. Då har vi ju hamnat i en motsägelse eftersom att $d > 1$ delar både $F_{k-1}$ och $F_{k}$ och saken är därmed klar.

Tack för hjälpen! Jag vet inte vems råd jag ska ta men jag ska kolla på båda exemplen. Jag börjar med din Freewheeling.

Jag har suttit lite på nätet och kollat efter fler tillväga sätt, för att jag tycker det är intressant. Kul med en uppgift där det finns många vägar för att lösa den. Jag hittade att vissa löser likande uppgifter med hjälp av matriser och determinater, jag tycker det låter intressant. Cassinis identitet. Tror ni man skulle kunna lösa denna uppgift med hjälp av detta också? :)

hej försöker lösa en liknade uppgift, skulle du kunna förklara lite mer hur du gjorde freewheeling.

Gabriella2001 skrev:
hej försöker lösa en liknade uppgift, skulle du kunna förklara lite mer hur du gjorde freewheeling.

Gör en ny tråd där du visar hur långt du har kommit, så är det lättare att hjälpa dig.

Svara

Visa senaste svar