Inlämningsuppgifter vecka 1

1

[Biggs 1.4.1] Använd induktionsprincipen för att bevisa att

1²+2²+...+n²=n(n+1)(2n+1)/6,

för alla positiva heltal n.

3

Lösning: För n=1 har vi att VL=1²=1 och HL= 1×(1+1)(2×1+1)/6 =1. Antag att påståendet är sant för n=k. Då får vi för n==k+1 att VL_k+1 =1²+2²+...+k²+(k+1)²=[enligt induktionsantagandet]=k(k+1)(2k+1)/6 + (k+1)²= (k+1)(k(2k+1) + 6(k+1)) /6 = (k+1)(2k²+k+6k+6) /6 =(k+1)(2k²+7k+6) /6 = (k+1)(k+2)(2k+3) /6=HL_k+1 eftersom (k+2)(2k+3) =2k²+4k+3k+6 =2k²+7k+6.

2

[Biggs 1.4.3] Använd den starka formen av induktionsprincipen för att visa att om följden u_n är definierad rekursivt genom

u₁=3, u₂=5 och u_n=3u_n-1 -2u_n-2 för n>2

så gäller att u_n=2ⁿ+1 för alla positiva heltal n.

3

Lösning: Vi har två startvärden att kontrollera. Det är u₁=2¹+1=3, u₂=2²+1=5, vilket båda stämmer med det angivna. Låt k>2 och antag nu att påståendet gäller för alla n<k. Vi får då enligt induktionsantagandet att

u_k=3u_k-1 -2u_k-2 = 3(2^k-1+1) – 2(2^k-2+1) = 6×2^k-2+ 3 – 2×2^k-2-2= 4×2^k-2+ 1 = 2^k+1

och därmed stämmer påståendet för alla n<k+1. Enligt induktionsprincipen gäller nu att u_n=2ⁿ+1 för alla positiva heltal n.

3

[Biggs 1.9.1] Använd induktionsprincipen för att visa att

2ⁿ>n+1,

för alla heltal n>1.

3

Lösning: För n=2 har vi att 2²=4 och att 2+1=3, alltså gäller 2²>2+1. Antag nu att påståendet gäller för något n=k. Då får vi att

2^k+1>= 2×2^k >2(k+1)=2k+2=(k+2)+ k> k+2

om k>0. Det följer av induktionsprincipen att 2ⁿ>n+1, för alla heltal n>1.

4

[Biggs 1.9.2] Visa att

1⁴+2⁴+...+n⁴ = n(n+1)(2n+1)(3n²+3n+1)/30

för alla positiva heltal n.

3

5

[Biggs 1.9.3] Visa att 4²ⁿ-1 är delbart med 15 för alla positiva heltal n.

3

För n=1har vi att 4^2×1-1 = 16-1=15, vilket är delbart med 15. Antag nu att 4^2k-1=15m för något m. Vi får då att

4^2(k+1)-1=16×4^2k- 1=16(15m+1)-1 = 15(16m+1),

och därmed är även 4^2(k+1)-1 delbart med 15. Enligt induktionsprincipen följer nu att 4²ⁿ-1 är delbart med 15 för alla heltal n>0.

6

[Biggs 1.9.4] Bestäm den största gemensamma delaren av 1320 och 714 och uttryck den på formen 1320 x + 714y där x och y är heltal.

3

Lösning: Med hjälp av Euklides algoritm kan vi bestämma den största gemensamma delaren.

1320 = 1×714 +606

714 = 1×606 +108

606 = 5×108 +66

108 = 1×66+42

66 = 1×42 +24

42 = 1×24 +18

24 = 1×18 +6

18 = 3×6 +0

Den största gemensamma delaren är alltså 6 och vi kan använda algoritmen baklänges för att skriva 6 som 1320 x + 714y där x och y är heltal.

6 = 24 - 1×18 = 24 - 1×(42-1×24 )

= 2×24 - 1×42= 2×(66- 1×42) - 1×42

= 2×66- 3×42=2×66- 3×(108- 1×66)

= 5×66 - 3×108 = 5×(606-5×108) - 3×108

= 5×606- 28×108 = 5×606- 28×(714- 1×606)

= 33×606- 28×714 = 33×(1320-1×714)- 28×714

= 33×1320-61×714

Alltså är sgd(1320,714)=6 =33×1320-61×714.

7

[Biggs 1.9.5] Visa att 725 och 441 är relativt prima och bestäm heltal x och y så att 725x+441y=1.

3

Lösning: Med hjälp av Euklides algoritm kan vi bestämma den största gemensamma delaren.

725 = 1×441 + 284

441 = 1×284 + 157

284 = 1×157 +127

157 = 1×127+30

127 = 4×30 +7

30 = 4×7 +2

7 = 3×2 +1

2 = 3×1 +0

Den största gemensamma delaren är alltså 6 och vi kan använda algoritmen baklänges för att skriva 6 som 1320 x + 714y där x och y är heltal.

1 = 7 - 3×2 = 7 - 3×(30-4×7 )

= 13×7 - 3×30= 13×(127- 4×30) - 3×30

= 13×127- 55×30=13×127- 55×(157- 1×127)

= 68×127 - 55×157 = 68×(284-1×157) - 55×157

= 68×284- 123×157 = 68×284- 123×(441- 1×284)

= 191×284- 123×441 = 191×(725-1×441)- 123×441

= 191×725-314×441

Alltså är sgd(725,441)=1 =191×725-314×441.

8

[Biggs 1.9.6] Bestäm alla lösningar till ekvationen

325x+26y=91

där x och y är heltal.

3

Lösning: Med hjälp av Euklides algoritm kan vi bestämma den största gemensamma delaren.

325 = 12×26+ 13

26 = 2×13 + 0

Om vi går baklänges får vi 13 = 1×325-12×26 och eftersom 91 = 7×13 kan vi lösa ekvationen med x=7×1=7 och y=7×(-12)=-84. För att få de andra lösningarna ser vi att sgd(325/13,26/13)=sgd(25,2)=1, och därmed ges alla andra lösningar av x=7-2k, y=-84+25k.

9

[Biggs 1.9.7] Följden f_n är rekursivt definierad genom

f₁=1, f₂=1,    och   f_n+1=f_n+f_n-1, för n>1.

Visa att sgd(f_n+1,f_n)=1 för alla positiva n.

6

Lösning: Det är klart att sgd(f_n+1,f_n)=1 för n=1, eftersom f₁=f₂=1. Vi antar nu att vi har visat att sgd(f_n+1,f_n)=1 för n=k. Vi får då att

sgd(f_k+2,f_k+1)=sgd(f_k+1+f_k,f_k+1)= sgd(f_k,f_k+1)=1, och vi får enligt induktionsprincipen att sgd(f_n+1,f_n)=1 för alla positiva n.

10

[Biggs 1.9.12] Bestäm alla positiva heltal n som har följande egenskaper:

(i) n är kvadratfri, dvs primfaktoriseringen av n har inga upprepade faktorer.

(ii) För alla primtal p gäller att p delar n om och endast om p-1 delar n.

6

Lösning: Med p=2 får vi enligt (ii) att 2 delar n eftersom 2-1=1 delar n. Eftersom 2 delar n får vi enligt (ii) att 3 delar n, eftersom 3-1=2 delar n. Nu har vi att 2×3=6 delar n, och med p=7 i (ii) får vi att 7 delar n. Nu måste 2×3×7=42 dela n och därmed p=43. Nu har vi kommit fram till att 2×3×7×43=1806 delar n. Om det finns någon fler primtalsfaktor i n, måste det finnas en minsta sådan, p. Eftersom p-1 också delar n, måste p-1 vara en kvadratfri produkt av primtalen 2, 3, 7 och 43. Om vi tar alla sådana produkter får vi; 1,2,3,6,7,14,21,42,43,86,126,252,295,602,903,1806. Eftersom det bara är bara 1,2,6 och 42 av dessa som är lika med p-1 för något primtal p, kan det inte finnas någon annan primtalsfaktor i n, och vi ser på samma gång att talet 1806 verkligen uppfyller villkoret.

11

[Biggs 1.9.17] Visa att det inte finns några heltal x, y, z, t för vilka

x² + y²-3z²-3t²=0

6

Lösning: Lösningen bygger på att vi kan se att en summa av två heltalskvadrater antingen inte är delbar med tre, eller är delbar med nio. Det kan vi se genom att skriva talen i bas tre och se att den sista siffran i en kvadrat alltid måste vara 0 eller 1. Om vi har en summa av två kvadrater får vi därmed sista siffran lika med noll bara om båda kvadaterna har sista siffra noll, men då är även den näst sista siffran noll.

När vi väl vet detta kan vi se att x² + y²-3z²-3t²=0 innebär att x² + y² är delbart med nio, och därmed kan vi dela båda x och y med tre för att få en ny ekvation 3x² + 3y²-z²-t²=0. Vi kan nu upprepa argumentet om och om till det inte går att dela med tre fler gånger, och vi ser då att det faktiskt inte finns någon lösning till ekvationen.