یک ردیف از $n$ صندلی داریم به طوری که روی هر کدام یک بچه نشسته است. هر بچه می‌تواند تا حداکثر یک صندلی تغییر مکان بدهد. تعداد آرایش‌های ممکن را بیابید.

فرض کنید شماره‌ی صندلی‌ها و بچه‌ها $1,2,\dots ,n$ باشد. $a_n$ را تعداد آرایش‌های ممکن آنها بگیرید.

اگر بچه‌ی اول سر جایش بماند، تعداد آرایش‌ها برابر $a_{n-1}$ است. (یعنی تعداد آرایش‌هایی که بچه‌ی اول سر جای خود است.)

اگر بچه‌ی شماره 1 به صندلی 2 برود، بچه‌ی شماره‌ی 2 باید به صندلیی 1 برود، در این حالت تعداد آرایش‌ها برابر $a_{n-2}$ ت.

بنابراین داریم

$a_n=a_{n-1}+a_{n-2}$

که $a_1=1$ و $a_2=2$. بنابراین $a_n=F_{n+1}$ که $F_n$، $n$-امین عدد فیبوناچی است.