מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/עצי חיפוש בינריים/תרגילים/נוסחת נסיגה למספר עצי שונים/שאלה

בשאלה זו עליך להוכיח חסם תחתון על $\displaystyle T(n)$, מספר עצי החיפוש הבינריים השונים בעלי $\displaystyle n$ מפתחות שונים זה מזה.

דוגמה: נניח שעץ החיפוש מכיל את המפתחות $\displaystyle 1,2$. יש 2 עצים מתאימים: עצי חיפוש בינריים בעלי המפתחות 1 ו2. נניח שעץ החיפוש מכיל את המפתחות $\displaystyle 1,2,3$. יש 5 עצים מתאימים: עצי חיפוש בינריים בעלי המפתחות 1, 2, ו3.

מהדוגמה נוכל להסיק כי

$\displaystyle T(0)=T(1)=1$, $\displaystyle T(2)=2$, $\displaystyle T(3)=5$.

אנא הוכח את המשפט הבא.

משפט: אם $\displaystyle n>1$, אז $\displaystyle T(n)=\sum _{i=0}^{n-1}[T(i)\cdot T(n-i-1)]$.