De ce contează?
Pui o pereche de iepuri într-o țarcă. În fiecare lună, fiecare pereche matură naște o nouă pereche, iar puii devin maturi după o lună. Numeri perechile la început de lună: 1, 1, 2, 3, 5, 8, 13... Fiecare număr e suma celor două dinainte, fiindcă populația de luna asta = cea de luna trecută (toate supraviețuiesc) + cei nou-născuți (câte una pentru fiecare pereche care era deja matură acum o lună). Același tipar îl vezi în spirala unei scoici sau în aranjarea petalelor.
Intuiția
Șirul lui Fibonacci pornește de la doi termeni egali cu 1, iar fiecare termen
nou e suma ultimilor doi: F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2). Nu trebuie
să reții tot istoricul: ca să afli termenul următor îți ajung exact ultimele două
valori. Imaginează-ți două ferestre care alunecă spre dreapta — la fiecare pas
aduni ce e în ele, scrii rezultatul și glisezi ferestrele mai departe.
Cheia întregii lecții: ții doar ultimele două valori. De îndată ce ai calculat
un termen nou, cel mai vechi dintre cei doi nu-ți mai trebuie niciodată — îl
arunci. Două variabile, oricât de mare ar fi n.