קנגורו עומד בפני גרם מדרגות ובו 20 מדרגות. בכל צעד הקנגורו יכול לקפוץ מדרגה אחת או שתי מדרגות. בכמה דרכים שונות יכול הקנגורו לעלות את גרם המדרגות?
פתרון
בצעד הראשון יכול הקנגורו לעלות מדרגה אחת או שתיים. כלומר, מספר האפשרויות לאחר מכן הוא מספר האפשרויות לעלות 19 מדרגות (שנותרו) ועוד מספר האפשרויות לעלות 18 מדרגות. באופן דומה אם A(n) מייצג את מספר הדרכים לטפס סולם בעל n שלבים אז מתקיימת נוסחת הנסיגה: A(n)=A(n-1)+A(n-2) שהיא בדיוק נוסחת הנסיגה של סדרת פיבונאצ'י. ולכן A(n)=1,2,3,5,8... מכאן שמספר האפשרויות לטפס 20 מדרגות הוא המספר ה-20 בסדרה שהינו 10,946.
