משתמש:טוקיוני/שיר אהבה למחשבה/מגדלי האנוי ואינדוקציה: הבדלים בין גרסאות בדף

אבל ראינו בדיוק איך ומתי מותר לנו להשתמש במילים 'וכך הלאה', ראינו שבשביל להשתמש במילים האלו אנחנו צריכים להוכיח את שני שלבי האינדוקציה. קודם כל אנחנו צריכים להראות שהכלל שגילינו הוא נכון עבור האיבר הראשון בסידרה. ואכן H)1(=2^1-1. שנית אנחנו צריכים להוכיח את שלב האינדוקציה, כלומר להראות שאם הנוסחא נכונה לאיבר הn, כלומר אם אכן H(n)=2^n-1 אזי הנוסחא גם נכונה לאיבר ה n+1. אבל זה קל להוכיח:

H(n+1)=2H(n)+1=2*(2^n-1)+1=2^)n+1)-1