שלב 8 מתוך 20

מכלל נסיגה לנוסחה מפורשת

נתון כלל נסיגה, ומוצעת נוסחה an=f(n)a_n=f(n). מוכיחים באינדוקציה שהנוסחה נכונה לכל nn:

11
בדיקה: a1a_1 הנתון שווה ל-f(1)f(1)
22
הנחה: ak=f(k)a_k=f(k)
33
הוכחה: מציבים את ההנחה בכלל הנסיגה, ומראים ש-ak+1=f(k+1)a_{k+1}=f(k+1)