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

הוכחה: נוכיח באינדוקציה שקיים $\displaystyle c>0$ כך ש$\displaystyle T(n)\geq c\cdot 1.5^{n}$.

(מעבר האינדוקציה) נניח שהטענה נכונה עד (כולל) $\displaystyle n-1$, ונוכיח שהיא נכונה ל$\displaystyle n$.‏ עפ"י נוסחת הנסיגה, $\displaystyle T(n)=\sum _{i=1}^{n-1}[T(i)]+\Theta (n)\geq \sum _{i=1}^{n-1}[T(i)]+c'\cdot n$
עבור $\displaystyle c'$ כלשהו. לכן, עפ"י הנחת האינדוקציה, $\displaystyle T(n)\geq \sum _{i=1}^{n-1}[c\cdot 1.5^{i}]+c'\cdot n$.
עפ"י הנוסחה לטור הנדסי,

$\displaystyle \sum _{i=1}^{n-1}[c\cdot 1.5^{i}]+c'\cdot n=$
$\displaystyle c\cdot 1.5^{1}(1.5^{n-1}-1)/(1.5-1)+c'\cdot n=$
$\displaystyle 2\cdot c\cdot 1.5^{1}(1.5^{n-1}-1)+c'\cdot n=$
$\displaystyle 2\cdot c\cdot 1.5^{n}-3\cdot c+c'\cdot n.$
אם ניקח $\displaystyle c<c'/3$,‏ אז הביטוי האחרון גדול מ$\displaystyle c\cdot 1.5^{n}$.

(בסיס האינדוקציה) היות ש$\displaystyle T(1)=O(1)$,‏ אז $\displaystyle T(1)=c_{0}$,‏ עבור $\displaystyle c_{0}>0$ כלשהו. נפתור $\displaystyle T(1)=c_{0}\geq c\cdot 1.5^{1}$,‏ ונקבל $\displaystyle c\leq c_{0}/1.5$.‏

האינדוקציה, לכן, נכונה עבור $\displaystyle 0<c<\min\{c_{0}/1.5,c'/3\}$, החל מ$\displaystyle n=1$.