MA 366: POTENSSUMMER

John Rognes

Mars 2000

Summer av potenstall

Potenstall. Et kvadrat med sidekanter av lengde n har areal n · n = n^{2}. Tall på formen n^{2} der n er et naturlig tall kalles kvadrattall. De er arealene til kvadrater med heltallige sidekanter. De 10 første kvadrattallene er 1, 4, 9, 16, 25, 36, 49, 64, 81 og 100.

En kube med sidekanter av lengde n har volum n · n · n = n^{3}. Tall på formen n^{3} der n er et naturlig tall kalles kubikktall. De er volumene til kuber med heltallige sidekanter. De 10 første kubikktallene er 1, 8, 27, 64, 125, 216, 343, 512, 729 og 1000.

La m være et naturlig tall. Tall på formen n^{m} der n er et naturlig tall kan vi kalle mte-potenstall. For m = 2 gir dette kvadrattallene, for m = 3 får vi kubikktallene, og for m = 4 kan vi også kalle fjerdepotenstallene bikvadrattall. For m = 1 er første-potenstallene bare det samme som de naturlige tallene. For m ≥ 5 har vi kanskje ikke noen egne navn for mte-potenstallene.

Summer av naturlige tall, triangeltall. En tidlig anekdote om matematikeren Carl Friedrich Gauss forteller at da hans skolelærer satte klassen til å addere sammen alle de hele tallene fra 1 til 100, og dermed regnet med å ha ro og fred en god stund fremover, skrev den unge Gauss umiddelbart ned svaret 5050 og brakte det frem til kateteret.

Gauss kjente altså en rask metode for å beregne summen av de n første naturlige tallene

1 + 2 + ⋯ + n = ∑_{k=1}^{n} k .

Dette er ikke noe annet enn summen av de n første første-potenstallene. Svaret er gitt ved formelen

∑_{k=1}^{n} k = \frac{n(n + 1)}{2} .

For eksempel er ∑_{k=1}^{100} k = 100 · 101/2 = 5050.

Tall på formen n(n + 1)/2 kalles triangeltall, fordi de gir antall sirkler i en triangulær form pakket sammen av like store tangerende sirkler, der det er n sirkler langs hver av de tre like lange sidekantene. Sirklene ligger da i n rader parallelle med en av kantene, og det er fra 1 til n sirkler i hver rad. Altså er det 1+2+⋯+n sirkler tilsammen. De 10 første triangeltallene er 1, 3, 6, 10, 15, 21, 28, 36, 45 og 55.

Typeset by AMS-TEX

Oppgave 1. Vis at ∑_{k=1}^{n} k = n(n + 1)/2 for n ≥ 0 ved følgende symmetrimetode:

La T (n) = 1 + 2 + ⋯ + n = ∑_{k=1}^{n} k. Da er også T (n) = n + (n − 1) + ⋯ + 1 = ∑_{k=1}^{n}(n + 1 − k). Ved å summere disse to uttrykkene ledd for ledd får vi

T (n) + T (n) = (1 + n) + (2 + (n − 1)) + ⋯ + (n + 1) = ∑_{k=1}^{n}(k + n + 1 − k) .

Her er det n ledd til høyre, og hvert ledd er lik n + 1. Så summen til høyre er n · (n + 1). Altså er 2T (n) = n(n + 1) og T (n) = n(n + 1)/2, som skulle vises.

Sjekk også ved summasjon at formelen er riktig for n = 10.

Summer av kvadrattall, pyramidetall. Tilsvarende kan man be om et uttrykk for summen av de n første kvadrattallene

1 + 4 + ⋯ + n^{2} = ∑_{k=1}^{n} k^{2} .

Den er gitt ved formelen

∑_{k=1}^{n} k^{2} = \frac{n(n + 1)(2n + 1)}{6} .

For eksempel er ∑_{m=1}^{100} m^{2} = 100 · 101 · 201/6 = 338.350.

Tall på formen n(n + 1)(2n + 1)/6 kalles pyramidetall, fordi de gir antall kuler i en pyramidal form med kvadratisk grunnflate, pakket sammen av like store kuler. Kulene ligger da i n kvadratiske nivåer parallelle med grunnflaten, og det er fra 1 til n^{2} kuler i hvert nivå. Til sammen er det 1 + 4 + ⋯ + n^{2} kuler i pyramiden. De 10 første pyramidetallene er 1, 5, 14, 30, 55, 91, 140, 204, 285 og 385.

Oppgave 2. Kom frem til formelen ∑_{k=1}^{n} k^{2} = n(n + 1)(2n + 1)/6 for n ≥ 0 ved de ukjente koeffisienters metode:

Siden triangeltallene T (n) er gitt som et annengradspolynom i n kan det tenkes at pyramidetallene kan skrives som et tredjegradspolynom i n. La P (n) = ∑_{k=1}^{n} k^{2} og anta at det finnes tall a, b, c og d slik at

P (n) = a · n^{3} + b · n^{2} + c · n + d

for alle hele tall n ≥ 0. Vi oppfatter a, b, c og d som ukjente, og for hvert naturlig tall n gir formelen ovenfor en likning som disse ukjente må oppfylle. Ved å sette inn ulike verdier for n får vi ulike likninger, og ved å bruke nok verdier for n kan vi entydig bestemme a, b, c og d, slik at formelen er riktig i hvert fall for disse verdiene av n.

Sett inn n = 0, n = 1, n = 2 og n = 3 i likningen ovenfor, og forklar hvorfor dette gir ligningssystemet

[ \begin{matrix}0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 \\ 8 & 4 & 2 & 1 \\ 27 & 9 & 3 & 1 \end{matrix} ] [ \begin{matrix}a \\ b \\ c \\ d \end{matrix} ] = [ \begin{matrix}0 \\ 1 \\ 5 \\ 14 \end{matrix} ] .

Løs ligningssystemet, finn a, b, c og d, og vis at an^{3}+bn^{2}+cn+d = n(n+1)(2n+1)/6.

Dette beviser ikke at formelen gjelder for alle n, men det viser at den er den eneste mulige formelen hvis P (n) skal være et tredjegradspolynom i n. Når man så har forslaget til formel foran seg kan den bekreftes ved et induksjonsbevis, som i oppgave 3.

Sjekk også ved summasjon at formelen er riktig for n = 10.

Summer av kubikktall. Vi kan fortsette. Summen av de n første kubikktallene

1 + 8 + ⋯ + n^{3} = ∑_{k=1}^{n} k^{3}

er lik kvadratet av summen av de n første naturlige tallene:

∑_{k=1}^{n} k^{3} = (\frac{n(n + 1)}{2})^{2} .

Dette synes å være et sammentreff, men er en grei huskeregel. De 10 første kubikktallsummene er 1, 9, 36, 100, 225, 441, 784, 1296, 2025 og 3025.

Oppgave 3. Vis at ∑_{k=1}^{n} k^{3} = (n(n + 1)/2)^{2} for n ≥ 0 ved induksjon:

La Q(n) = ∑_{k=1}^{n} k^{3} være summen av de n første kubikktallene. Vis først at Q(n) = (n(n + 1)/2)^{2} er riktig for n = 0. Anta så at formelen gjelder for en verdi av n ≥ 0, og vis at den da også gjelder med n + 1 innsatt for n. Forklar hvorfor dette beviser at formelen gjelder for alle naturlige tall n.

Sjekk dette ved direkte summasjon for n = 10.

Summer av fjerdepotenstall. De 10 første fjerdepotenstallene er 1, 16, 81, 256, 625, 1296, 2401, 4096, 6561 og 10000. De 10 første fjerdepotenstallsummene er 1, 17, 98, 354, 979, 2275, 4676, 8772, 15333 og 25333. Deler vi disse på de tilsvarende pyramidetallene og ganger med 5 får vi noe overraskende en rekke hele tall: 5, 17, 35, 59, 89, 125, 167, 215, 269 og 329. Vi kunne kanskje ha forventet å få brøker med varierende nevnere. Igjen synes dette å være et sammentreff.

Oppgave 4. Vis at summen av de n første fjerdepotenstallene (= bikvadrattallene) er

B(n) = ∑_{k=1}^{n} k^{4} = \frac{n(n + 1)(2n + 1)(3n^{2} + 3n − 1)}{30}

= P (n) · \frac{3n^{2} + 3n − 1}{5} ,

ved følgende differens-metode:

La a_{1}, a_{2}, …, a_{n}, … være en tallfølge, med delsummer s_{0} = 0, s_{1} = a_{1}, s_{2} = a_{1} + a_{2} og generelt s_{n} = ∑_{k=1}^{n} a_{k} for n ≥ 0. Om vi har en formel for rekken av delsummer s_{n} for n ≥ 0 kan vi rekonstruere tallfølgen a_{n} for n ≥ 1 ved formelen a_{n} = s_{n} − s_{n−1}.

Selv om vi ikke umiddelbart kan skrive opp hva summen av de n første fjerdepotenstallene er, så kan vi finne en annen tallfølge av tall a_{n}, som er nært knyttet til fjerdepotensene, og som er slik at det er lett å beskrive delsummene s_{n}.

La s_{n} = n^{5} for n ≥ 0, og definer a_{n} = s_{n} − s_{n−1} for n ≥ 1. Vis at

a_{n} = 5n^{4} − 10n^{3} + 10n^{2} − 5n + 1 .

Følgen av tall a_{1} = 1, a_{2} = 31, a_{3} = 211 er da nært knyttet til følgen av fjerdepotenser. Fordelen med denne følgen er at dens delsummer er kjent: ∑_{k=1}^{n} a_{k} = s_{n} = n^{5}.

Vis så at

n^{5} = 5B(n) − 10Q(n) + 10P (n) − 5T (n) + n

der n^{5} = ∑_{k=1}^{n} a_{k}, B(n) = ∑_{k=1}^{n} k^{4}, Q(n) = ∑_{k=1}^{n} k^{3}, P (n) = ∑_{k=1}^{n} k^{2} og T (n) = ∑_{k=1}^{n} k som før. Sett inn de kjente uttrykkene for Q(n), P (n) og T (n) og vis at

B(n) = ∑_{k=1}^{n} k^{4} = \frac{1}{5}n^{5} + \frac{1}{2}n^{4} + \frac{1}{3}n^{3} − \frac{1}{30}n

= \frac{n(n + 1)(2n + 1)(3n^{2} + 3n − 1)}{30} .

Oppgave 5. Finn en formel for summen av de n første femtepotenstallene

F (n) = ∑_{k=1}^{n} k^{5} .

Hint: Tre ganger svaret er summen av de n første kubikktallene, ganger et annengradspolynom i n med heltallige koeffisienter.

Oppgave 6. Finn en formel for summen av de n første sjettepotenstallene

S(n) = ∑_{k=1}^{n} k^{6} .

Hint: Syv ganger svaret er det nte pyramidetallet ganger et fjerdegradspolynom i n med heltallige koeffisienter.

Bernoulli-tall

For å unngå noen fortegn senere, endrer vi perspektivet litt og ser på summen av de (n − 1) første kte-potenstallene, i stedet for de n første. Jacob Bernoulli (1654–1705) kjente formlene

∑_{k=1}^{n−1} k = \frac{1}{2}n^{2} − \frac{1}{2}n

∑_{k=1}^{n−1} k^{2} = \frac{1}{3}n^{3} − \frac{1}{2}n^{2} + \frac{1}{6}n

∑_{k=1}^{n−1} k^{3} = \frac{1}{4}n^{4} − \frac{1}{2}n^{3} + \frac{1}{4}n^{2}

∑_{k=1}^{n−1} k^{4} = \frac{1}{5}n^{5} − \frac{1}{2}n^{4} + \frac{1}{3}n^{3} − \frac{1}{30}n

∑_{k=1}^{n−1} k^{5} = \frac{1}{6}n^{6} − \frac{1}{2}n^{5} + \frac{5}{12}n^{4} − \frac{1}{12}n^{2}

∑_{k=1}^{n−1} k^{6} = \frac{1}{7}n^{7} − \frac{1}{2}n^{6} + \frac{1}{2}n^{5} − \frac{1}{6}n^{3} + \frac{1}{42}n

∑_{k=1}^{n−1} k^{7} = \frac{1}{8}n^{8} − \frac{1}{2}n^{7} + \frac{7}{12}n^{6} − \frac{7}{24}n^{4} + \frac{1}{12}n^{2}

∑_{k=1}^{n−1} k^{8} = \frac{1}{9}n^{9} − \frac{1}{2}n^{8} + \frac{2}{3}n^{7} − \frac{7}{15}n^{5} + \frac{2}{9}n^{3} − \frac{1}{30}n

∑_{k=1}^{n−1} k^{9} = \frac{1}{10}n^{10} − \frac{1}{2}n^{9} + \frac{3}{4}n^{8} − \frac{7}{10}n^{6} + \frac{1}{2}n^{4} − \frac{3}{20}n^{2}

∑_{k=1}^{n−1} k^{10} = \frac{1}{11}n^{11} − \frac{1}{2}n^{10} + \frac{5}{6}n^{9} − n^{7} + n^{5} − \frac{1}{2}n^{3} + \frac{5}{66}n

for eksponenter opp til 10. (Med forbehold om trykkfeil !) Det er kanskje klart at det er visse mønstre her, men det generelle mønsteret er antageligvis ikke helt åpenbart.

La S_{m}(n) = ∑_{k=1}^{n−1} k^{m} for m ≥ 1 og n ≥ 1. Vi ønsker, som Jacob Bernoulli, å komme frem til en formel for S_{m}(n) som et (m + 1)-tegradspolynom i n med rasjonale koeffisienter.

Bruk binomialformelen

(j + 1)^{m+1} − j^{m+1} = 1 + ∑_{k=1}^{m} \binom{m + 1}{k}j^{k}

for å vise at

n^{m+1} = ∑_{j=0}^{n−1} ((j + 1)^{m+1} − j^{m+1})

= n + ∑_{j=0}^{n−1} ∑_{k=1}^{m} \binom{m + 1}{k}j^{k}

= n + ∑_{k=1}^{m} \binom{m + 1}{k} ∑_{j=0}^{n−1} j^{k}

= n + ∑_{k=1}^{m} \binom{m + 1}{k}S_{k}(n) .

Skill ut leddet k = m for å vise at

(†)  (m + 1)S_{m}(n) = n^{m+1} − ∑_{k=1}^{m−1} \binom{m + 1}{k}S_{k}(n) − n .

Dette er en rekursiv formel som kan brukes for å beregne S_{m}(n) for alle m ≥ 1.

Oppgave 7. Bruk den rekursive formelen (†) til å sjekke de ‘kjente’ formlene for S_{m}(n) for m = 1, 2, 3.

Oppgave 8. Rekonstruer utledningen av den rekursive formelen (†), uten å kikke !

Oppgave 9. Vis (ved induksjon) at S_{m}(n) er et (m + 1)-tegradspolynom i n med rasjonale koeffisienter.

Oppgave 10. Vis at S_{m}(n) har konstantledd lik 0, at koeffisienten for n^{m+1} er 1/(m + 1), at koeffisienten for n^{m} er −1/2, og at koeffisienten for n^{m−1} er m/12 for m ≥ 2.

Bernoulli innså at det er fruktbart først å bestemme koeffisienten for n i S_{m}(n).

Definisjon. Bernoulli-tallene B_{0}, B_{1}, B_{2}, … er rasjonale tall rekursivt definert som følger: B_{0} = 1 og hvis B_{1}, B_{2}, …, B_{m−1} allerede er kjent så er B_{m} bestemt ved likningen

(m + 1)B_{m} = − ∑_{k=1}^{m−1} \binom{m + 1}{k}B_{k} − 1

= − ∑_{k=0}^{m−1} \binom{m + 1}{k}B_{k}

for m ≥ 1.

Oppgave 11. Vis at B_{m} er koeffisienten for n i S_{m}(n).

Oppgave 12. Finn så mange som du orker av de 21 første Bernoulli-tallene: 1, −1/2, 1/6, 0, −1/30, 0, 1/42, 0, −1/30, 0, 5/66, 0, B_{12} = −691/2730, 0, 7/6, 0, −3617/510, 0, 43867/798, 0 og −174611/330.

Oppgave 13. Vis at summen av tiendepotensene av heltallene fra 1 til 1000 er

S_{10}(1001) = 91.409.924.241.424.243.424.241.924.242.500 .

Hint: Regn ut S_{10}(1000) først. Legg til 10^{30}.