De ce contează?
Urci o scară și poți face, la fiecare pas, fie o treaptă, fie două deodată. În
câte feluri ajungi pe treapta a 10-a? Gândește invers: pe ultima treaptă ai
ajuns ori dintr-un pas de o treaptă, ori dintr-un pas de două. Deci numărul de
trasee până la treapta n e suma traseelor până la n-1 și până la n-2. Ai
descoperit, fără să vrei, o relație de recurență — exact cea a lui Fibonacci.
Intuiția
O relație de recurență definește fiecare termen al unui șir folosind termenii
dinaintea lui, plus câțiva termeni inițiali de la care pornește totul. Cel mai
cunoscut exemplu este șirul lui Fibonacci: pleci de la F(0) = 0 și F(1) = 1,
iar de acolo fiecare termen e suma celor doi dinaintea lui, F(n) = F(n-1) + F(n-2).
Așa apar 0, 1, 1, 2, 3, 5, 8, 13, ... — fiecare număr „construit” din cele de sub el.