Insändningsuppgifter 3

1. Frivillig! Beräkna summan S_n = 1^.4 + 2^.7 + ... + n(3n + 1),
   då man vet att S_n = an³ + bn² + cn, där a, b och c är konstanter.
   (Uppgift 4.11, sid. 102.)
   Problemet kan också formuleras: Bestäm de tre konstanterna a, b och c genom att sätta in n = 1, 2 och 3. Bevisa sedan formeln med induktionsbevis.
   
2. Bevisa att 2ⁿ > n³ för alla heltal n > 9.
   (Uppgift 4.14, sid. 102.)
   
   
3. Undersök talen a_n definierade av a_o = 1/2,
   a_n+1 = a_n/(1 + a_n) för n = 0,1,2,... (Exempel 4.1, sid. 103)
   Försök finna en formel för dem av typen a_n = f(n) där f(n) är ett uttryck som bara beror på a_n (men inte på t.ex. a_n-1. Bevisa eventuella påståenden med induktionsbevis.
   
   
4. Visa att Fibonaccis tal (Exempel 4.2, sid. 103) uppfyller olikheten
   F_n < (7/4)ⁿ,    n = 1,2,3,...

   (Uppgift 4.25, s. 104, där dock exponenten har ändrats.
   OBS Ledning på sid. 284,
   som är korrekt för denna uppgift.)
   
   
   

5. Givet siffrorna 1, 2, 4, 5, 7. Om varje siffra får användas en gång, hur många tresiffriga tal kan man bilda av dessa siffror
   a) överhuvud taget,
   b) om talen skall vara udda
   c) om talen skall vara jämna,
   d) om talen skall vara delbara med 5?
   (Uppgift 5.6, sid. 111.)
   
   
6. Hur många "ord" omfattande 7 bokstäver kan erhållas av ordet UPPSALA?
   (Uppgift 5.8, sid. 113.)
   
   
7. En boksamling omfattar 5 böcker på svenska, 4 på engelska och 3 på franska. På hur många sätt kan samlingen ställas upp på en bokhylla, om böcker på samma språk skall stå intill varandra?
   (Uppgift 5.13. sid. 114.)
   
   
8. Ett politiskt parti har två olika röstsedlar, A med 8 namn och B med 6 namn.
   Man vill göra en samlingslista med dessa 14 namn, så att den ursprungliga ordningsföljden mellan namnen från A bibehålls, liksom ordningen mellan namnen från B, medan däremot ordningen mellan ett namn frän A och ett namn från B är likgiltig.
   På hur många sätt kan en sådan lista göras?
   (Uppgift 5.20, sid. 119.)
   
   
9. Bevisa att 2^k = 3ⁿ för alla naturliga tal n. (Uppgift 5.28, sid. 122))
   eller
   bestäm koefficienten för a³b⁶c³ i utvecklingen av (a + b² + c³)^{7 .}
   (Uppgift 5.29, sid. 122.)
   
   
   
10. Bevisa att i en godtycklig graf måste antalet noder med udda gradtal vara jämnt.
    (Uppgift 5.33, sid. 129. OBS tips på sid. 284)
    
    
11. Vilka av följande figurer går att rita med en penna som aldrig lyfts från papperet och så att inga streck dras mer än en gång?

    
    Uppgift 5.39, sid. 132. (Utför uppritningen eller motivera på annat sätt.)
    
    

12. Bestäm en Hamiltoncykel i grafen Q₃ (sid. 128) av hörnen och kanterna i en vanlig kub.
    Uppgift 5.41, sid. 132.