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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש

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

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





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


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

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

מש"ל.PNG