על-מנת להבין את ההוכחה צריך ידע קודם באלגברה לינארית.
תחילה נגדיר סדרת מספרים ${\displaystyle a_{0},a_{1},a_{2},\cdots }$ באופן רקורסיבי: ${\displaystyle a_{0}=0,a_{1}=1}$ ו- ${\displaystyle a_{k+1}=a_{k}+a_{k-1}}$.