Maar goed, dit was een makkie, een veel
interessantere vraag is natuurlijk:
| Hoeveel
ECHT verschillende sommen zijn er waar
20 uit komt? |
Want wees nou eerlijk: 4 + 14 + 2 is natuurlijk
hetzelfde als 2 + 4 + 14.
Noem P(n) het aantal ECHT verschillende manieren.
Bijvoorbeeld P(5) = 7, namelijk 5 , 4+1 , 3+2,
3+1+1 , 2+2+1 , 2+1+1+1 en 1+1+1+1+1
Dat aantal is echter in het algemeen niet zo simpel te berekenen!
Goldbach schreef een brief aan Euler waarin hij hem vroeg naar
de waarden van P(n). Creatief als altijd, produceerde
Euler een methode om functies te genereren voor een antwoord op de
vraag.
En hij kwam tot een verrassende ontdekking!
|
De ontdekking van Euler
Een verrassende en geniale ontdekking van Euler ging in drie
stappen:
STAP 1
Hij beschouwde het oneindige product:
(1 + x) (1 + x2) (1 + x3)
(1 + x4) ......
Als je alle haakjes weg zou werken wordt de coλfficiλnt van xn
precies gelijk aan A(n) !!!
Kijk maar hieronder:
|
|
|
|
de factor zonder x wordt 1 (van 1 1 1 ...)
de factor bij x1 wordt ook 1 (van x 1
1 ...)
de factor bij x2 wordt 1 (van 1 x2)
de factor bij x3 wordt 2 (van x3 +
x2+1)
de factor bij x4 wordt 2 (van x4 +
x3+1) ofwel 4 = 3 + 1
de factor bij x5 wordt 3 (van x5
+ x4+1 + x3+2) ofwel 5
= 4 + 1 = 3 + 2
de factor bij x6 wordt 4 (van x6 +
x5+1 + x4+2 + x3+3)
ofwel 6 = 5 + 1 = 4 + 2 = 3 + 3
enz.
|
|
STAP 2
Beschouw de volgende meetkundige rij:
|
S |
= 1 + a + a2 + a3
+ a4 + ..... |
|
| dan geldt: |
a S |
= a
+ a2 + a3 + a4
+ a5 + ... |
|
| dus |
S - a S |
= 1 |
|
| S (1 - a) = 1 ή |
|
|
|
| Laten we a nu vervangen door oneven
machten van x, dan vinden we achtereenvolgens bijv. |
|
|
 |
|
|
 |
|
|
|
|
|
enz.
Definieer nu een nieuwe functie Q(x): |
|
|
|
|
|
Dan kunnen we deze Q(x) met de formules erboven anders
schrijven als:
Q(x) = (1 + x1 + x1+1 +
...)(1 + x3 + x3+3 + ...)(1
+ x5 + x5+5 + ...) ....
Als we nu de haakjes wegwerken en gelijke machten van x bij
elkaar zetten dan vinden we (op dezelfde manier als hierboven):
de factor bij 1 wordt 1
de factor bij x wordt 1
de factor bij x2 wordt 1 (van x1+1)
de factor bij x3 wordt 2 (x1+1+1 +
x3) ofwel 3 = 1+1+1
de factor bij x4 wordt 2 (x1+1+1+1
+ x1+3) ofwel 4 = 1+1+1+1 = 3+1
de factor bij x5 wordt 3 (x1+1+1+1+1
+ x1+1+3 + x5) ofwel 5
= 1+1+1+1+1 = 1+1+3
de factor bij x6 wordt 4 (x1+1+1+1+1+1
+ x1+1+1+3 + x3+3 + x5)
ofwel ....
We ontdekken het volgende: Q(x) is het aantal manieren
waarop getal x als som van oneven getallen geschreven kan
worden.
STAP 3
Het lijkt erop dat geldt Q(x) = P(x)
Dat bewees Euler als volgt:
|
|
|
|
= (1+x) (1 + x2) (1 + x4)
...
= P(x) |
|
|
|
De ontdekking van Euler:
| Het aantal verschillende
sommen waar n uitkomt is hetzelfde als het aantal
manieren waarop n als som van oneven getallen
geschreven kan worden!!! |
Toegegeven, je hebt er verder niets aan, maar 't is wel een
geweldig mooi bewijs!
Het berekenen van het aantal echt verschillende sommen waar n
uitkomt kan ook wel op een simpelere manier. Noem Pk(n)
het aantal sommen met k of minder termen.
Dan kunnen we recursievergelijkingen voor Pk opstellen als
we het volgende bedenken:
| 1. |
Het aantal sommen met k
of minder termen is gelijk aan het aantal met exact k
termen plus het aantal met k -1 of minder termen. |
| 2. |
Als we een verdeling van n
in exact k termen hebben, dan kunnen we 1 van elke term
aftrekken en dan hebben we een verdeling van n - k in
exact k termen. Er is een 1-op-1 relatie tussen de
sommen van n in exact k termen en de sommen van
n - k in k of minder termen. |
Dat geeft de volgende recursievergelijking:
|
| Pk(n) =Pk-1(n)
+ Pk(n - k) |
|
Daarmee maken we makkelijk de volgende tabel:
| n |
|
k |
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -1 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
| 0 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
| 1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
| 2 |
|
1 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
| 3 |
|
1 |
2 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
| 4 |
|
1 |
3 |
4 |
5 |
5 |
5 |
5 |
5 |
5 |
5 |
5 |
5 |
5 |
5 |
| 5 |
|
1 |
3 |
5 |
6 |
7 |
7 |
7 |
7 |
7 |
7 |
7 |
7 |
7 |
7 |
| 6 |
|
1 |
4 |
7 |
9 |
10 |
11 |
11 |
11 |
11 |
11 |
11 |
11 |
11 |
11 |
| 7 |
|
1 |
4 |
8 |
11 |
13 |
14 |
15 |
15 |
15 |
15 |
15 |
15 |
15 |
15 |
| 8 |
|
1 |
5 |
10 |
15 |
18 |
20 |
21 |
22 |
22 |
22 |
22 |
22 |
22 |
22 |
| 9 |
|
1 |
5 |
12 |
18 |
23 |
26 |
28 |
29 |
30 |
30 |
30 |
30 |
30 |
30 |
| 10 |
|
1 |
6 |
14 |
23 |
30 |
35 |
38 |
40 |
41 |
42 |
42 |
42 |
42 |
42 |
| 11 |
|
1 |
6 |
16 |
27 |
37 |
44 |
49 |
52 |
54 |
55 |
56 |
56 |
56 |
56 |
| 12 |
|
1 |
7 |
19 |
34 |
47 |
58 |
65 |
70 |
73 |
75 |
76 |
77 |
77 |
77 |
| 13 |
|
1 |
7 |
21 |
39 |
57 |
71 |
82 |
89 |
94 |
97 |
99 |
100 |
101 |
101 |
| 14 |
|
1 |
8 |
24 |
47 |
70 |
90 |
105 |
116 |
123 |
128 |
131 |
133 |
134 |
135 |
De blauwe 70 is bijvoorbeeld berekend door de blauwe 65 en de blauwe 5
bij elkaar op te tellen. In het groen is hetzelfde gebeurd.
De rode diagonaal is nu precies het aantal manieren om echt
verschillende sommen te maken waar n uitkomt!
De tabel
uitbreiden geeft als diagonaal:
1,2,3,5,7,11,15,22,30,42,56,77,101,135,176,231,297,385,490,627 Conclusie:
"Er zijn 627
echt verschillende sommen waar 20 uitkomt" |
