De oplossing

Zoals een aantal lezers door middel van dubbele inductie aantoonde verscheen vorige week (De manier) mijn laatste puzzel...

HANS QUENE

Dat zat zo:

De som van alle gehele getallen van 1 tot en met n noem ik S(n). Van deze som weet ik twee dingen: S(0) = 0 en S(n+1) = S(n)+n+1. Deze twee beweringen samen zijn voldoende om S(n) te definiëren. Het laatste zegt bijvoorbeeld dat je S(100) kan berekenen door eerst S(99) te berekenen en daar dan 100 bij op te tellen. Dat is een waarheid als een koe, maar tegelijkertijd iets om wanhopig van te worden. Want hoe bereken je S(99)? De definitie vertelt niets meer dan dat je dan maar eerst S(98) moet berekenen en daar dan 99 bij op moet tellen. Je weet pas echt iets als je zo bent afgezakt tot S(0), en dan moet het berekenen van de honderd deelsommen nog beginnen.

We willen S(n) dus ook graag in een wat handzamer formaat. Hoe dat zou kunnen leren we van een voorbeeld:

S(6) = 1+2+3+4+5+6 = (1+6) +(2+5)+(3+4) = 7+7+7 = 37 = 21.

Bij een ander even getal tel je geen drie getallen bij elkaar op, maar n/2. Het gaat dan niet om zevens, maar om (n+1)'s. Het produkt is de interessante functie F(n) = n(n+1)/2. Het zou wel eens kunnen dat voor een heleboel verschillende n's geldt dat F(n) = S(n). Als n even is weten we dat al haast zeker.

We berekenen F(n+1). Dat doen we direct, door in de formule voor F(n) elke n te vervangen door (n+1). F(n+1) = (n+1)(n+2)/2. We berekenen bovendien F(n) + (n+1).

Dat is n(n+1)/2 + (n+1) = (n+1)(n+2)/2. De uitkomsten zijn gelijk, zodat F(n+1) = F(n)+(n+1). Bovendien geldt F(0) = 0.

F(n) lijkt dus als twee druppels water op S(n). Voor F(n) gelden dezelfde twee beweringen als bij de defintie van S(n). Maar dan ìs F(n) gewoon S(n). S(n) = n(n+1)/2. We weten nu zeker dat dit geldt voor elke gehele n vanaf 0.

Hetzelfde kunstje kan met C(n), de som van de eerste n kubussen. Als definitie van C(n) dient C(0) = 0 en C(n+1) = C(n)+(n+1)3. Als 'interessante functie' komt na enige aarzeling in aanmerking G(n) = n2(n+1)2/4, want dat is het kwadraat van S(n), en dat werkte zo goed voor kleinere n. Dan is G(n+1) = (n+1)2(n+2)2/4, en G(n+1) = G(n)+(n+1)3, G(0) = 0. De functies zijn gelijk. Dan geldt ook C(n) = S2(n), voor elke gehele n groter dan 0.

Dit laatste was precies de bewering van het buurmeisje. Er was dus niets mis met haar manier van berekenen.

Het is onmogelijk om een tegenvoorbeeld te vinden, en zeker niet een onder de 100.000. Omdat er nul uitzonderingen waren zouden er maximaal nul puzzels verschijnen.

Het werd voor mij tijd om eens om te zien naar een echte baan.

Meer over