Berekeningsmethoden (8)
Fn+1 = F1 + F2 + F3 + ... + Fn-1 + 1.
De laatste term 1 komt van het feit dat het natuurlijk ook mogelijk is dat er totaal geen 1 bij 2 stenen worden gebruikt.
Dus g1,n = Fn+2 - 1
We zullen nu een uitdrukking voor g2,n proberen te vinden.
We maken ook hier weer gebruik van het padenprobleem uit de inleiding:
Leg nu 2 parallelle paden. Bij het linker pad laten we de laatste n-de plek weg. Het aantal mogelijke paden (patronen)
is dus FnFn+1. We kijken nu waar de laatste 1 bij 1 steen ligt. Daarvoor zijn alleen de volgende plaatsen mogelijk:
Op de n-de plek van het rechter pad; op de n-1-ste plek van het linker pad; op de n-2-de plek van het rechter pad;
op de n-3-de plek van het linker pad, enz. Stel nu dat de laatste 1 bij 1 steen op de i-de plek ligt, dan kan het overige deel (vóór de i-de plek)
in beide paden op Fi manieren zijn gelegd, dus in totaal op Fi2 manieren. We vinden dus, door alle mogelijke waarden voor i te doorlopen, dat
FnFn+1 = F12 + F22 + ... + Fn2
