כרגיל, מותר לנו לקבוע ש
עבור קבוע
כלשהו, וזאת משום ש
מתארת את זמן הריצה של אלגוריתם.
נוכיח ש
. ליתר דיוק, נוכיח באינדוקציה שקיים
כך ש
.
הוכחה: (בסיס האינדוקציה) עבור
, נקבל
, כלומר כל שצריך הוא לבחור
המקיים
.
(מעבר האינדוקציה) נניח שהטענה נכונה עד (כולל)
, ונוכיח שהיא נכונה עד (כולל)
. מהצבה בנוסחת הנסיגה, נקבל 
עבור
, נקבל
.
לסיכום, עבור
, הן בסיס האינדוקציה והן מעבר האינדוקציה מתקיימים.
נוכיח ש
. ליתר דיוק, נוכיח באינדוקציה שקיים
כך ש
.
הוכחה: (בסיס האינדוקציה) עבור
, נקבל
, כלומר כל שצריך הוא לבחור
המקיים
.
(מעבר האינדוקציה) נניח שהטענה נכונה עד (כולל)
, ונוכיח שהיא נכונה עד (כולל)
. מהצבה בנוסחת הנסיגה, נקבל 
עבור
, נקבל
.
לסיכום, עבור
, הן בסיס האינדוקציה והן מעבר האינדוקציה מתקיימים.
עלינו להוכיח שפתרון נוסחת הנסיגה
הוא
. אפשר לעשות זאת בכסעיף הקודם, אך נבחר לעשות זאת (שרירותית) בדדוקציה. נרשום 
