| Te bewijzen : | Voor elk natuurlijk getal n > 13 bestaan er natuurlijke getallen x en y zodanig dat n = 3x + 8y |
| m.a.w. | Elk geheel bedrag vanaf 14 reusos kan exact betaald worden met stukken van 3 en 8 reusos |
| Bewijs : | |
| Deel I |
Voor de kleinste n-waarde, nl. 14 bestaan x en y : 14 = 3.2 + 8.1 |
| Deel II | Gegeven : | Voor k (>13) bestaan x en y zodanig dat k = 3x + 8y ( I.H.) |
| Te bewijzen: | Voor k+1 bestaan er ook (andere) getallen x en y zodanig dat k = 3x + 8y | |
| Bewijs : |
Uit de inductiehypothese weten we dat er een x en een y bestaat zodanig dat k = 3x + 8y, dus ook zodanig dat k+1 = 3x+8y + 1. (*) We gaan nu twee gevallen onderscheiden : y = 0 en y ≠ 0. (Als het niet zou lukken, bv. bij een ander voorbeeld, neem dat x = 0 en x ≠ 0) | |
| __
Geval 1 : y ≠ 0, dus y minstens gelijk aan 1 Uit (*) volgt : k+1 = 3x + 8y + 1 = 3x + 8y + 1 + 8 − 8 = 3x + 9 + 8y − 8 = 3(x+3) + 8(y − 1) m.a.w. k+1 kan in de vorm 3n+8m geschreven worden met n=x+3 en m=y−1 (≥0) | ||
| __
Geval 2 : y = 0 We mogen in dit geval ervan uitgaan dat x minstens 5 is : voor x=4 krijgen we immers 4.3 = 12 < 13, voor x=5 5.3 = 15 > 13 Uit (*) volgt : k+1 = 3x + 1 = 3x − 15 + 15 + 1 = 3(x − 5) + 16 = 3(x− 5) + 8.2 m.a.w. ook hier zien we dat k+1 kan geschreven worden als 3n+8m met n=x− 5 en m=2 | ||
| __
Besluit : k + 1 kan (als k > 13) altijd geschreven worden als 3x + 8y met x,y ∈ ℕ |