Getalrepresentaties (3)
Als elk getal geschreven kan worden als som van verschillende Fibonaccigetallen, dan kunnen we ons de vraag stellen op hoeveel
manieren een getal a kan worden gerepresenteerd. Laten we dit aantal aangeven met m(a).
Stel k en n zijn (positieve gehele) getallen en k<Fn.
We onderzoeken de representatie van a = Fn+2 - k.
We bekijken eerst die representaties waarin de term Fn+1 niet voorkomt. We weten, dat
F1 + F2 + F3 + ... + Fn = Fn+2 - 1, (***)
dus kunnen we alle representaties zonder term Fn+1 vinden door
eerst alle representaties van k-1 op te sommen en die van deze representatie (***) af te trekken.
Nu nog de representaties met een term Fn+1. Er geldt dan a = Fn+1 + Fn - k.
Dit aantal is dus m(Fn - k).
Kortom: m(Fn+2 - k) = m(k-1) + m(Fn - k)
De formule is ook juist voor k=0 als we definieren m(-1)=1.
