Oppgave 1

Vi bruker som induksjonshypotese at påstanden er sann for alle k fra 1 til n. Den er sann for n = 1 og vi skal vise at den er sann for n + 1.

La 1 ≤ k ≤ n. Anta at vi har en rekkefølge av tallene fra 1 til n + 1 der det er nøyaktig k tall foran n + 1. Hvis vi permuterer de k første tallene i denne rekkefølgen på alle mulige måter, sier induksjonshypotesen at vi får en antallsum på tall som er større enn den største foran på k! · (H_k − 1). Men tallet n + 1 etterpå gir ett tall mer som er større enn det største foran. Antallsummen blir dermed k! · (H_k − 1) + k! = k! · H_k . Det finnes C(n,k) måter å velge k tall blant tallene fra 1 til n. Obs: C(n,k) er binomialkoeffisienten. De n − k tallene etter n + 1 kan permuteres på (n − k)! måter. Dermed

  B(n + 1 , k)   =   C(n,k) · k! · H_k · (n − k)!   =   n! · H_k .

Nå trenger vi flg. formel:

  H₁  +  H₂  +  H₃  +  ·  ·  ·  ·  +  H_n   =   (n + 1)(H_{n + 1} − 1)

Ved hjelp av denne formelen får vi at summen av B(n + 1 , k) fra 1 til n blir:

  n! · (n + 1)(H_{n + 1} − 1)   =   (n + 1)! · (H_{n + 1} − 1)

Dermed er påstanden sann for n + 1.