מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/נוסחאות נסיגה/תרגילים/נוסחת נסיגה לבעיית "דג הסלמון"/תשובה

הוכחה: נוכיח באינדוקציה שקיים כך ש.

(מעבר האינדוקציה) נניח שהטענה נכונה עד (כולל) , ונוכיח שהיא נכונה ל.‏ עפ"י נוסחת הנסיגה,
עבור כלשהו. לכן, עפ"י הנחת האינדוקציה, .
עפ"י הנוסחה לטור הנדסי,





אם ניקח ,‏ אז הביטוי האחרון גדול מ.


(בסיס האינדוקציה) היות ש,‏ אז ,‏ עבור כלשהו. נפתור ,‏ ונקבל .‏

האינדוקציה, לכן, נכונה עבור , החל מ.