שאלה פשוטה שהסתבכתי איתה

[loresin1]

שאלה פשוטה שהסתבכתי איתה

השאלה:

"נסח נוסחת נסיגה עבור מספר תתי הקבוצות של:

{1,2,3,...,n}​

שאין בהן 3 מספרים עוקבים".

ניסיתי להסתכל על זה מכל זווית כמעט- וכל פעם הרגשתי שאני קרוב, אבל לא מגיע לפתרון.
אודה לעזרתכם

 

[עריסטו]

ככה

כדי לקבל תת-קבוצה חוקית של {1,2,3,...,n} יש שלוש אפשרויות:

לוקחים תת-קבוצה חוקית של המספרים בין 1 ל-n-1, ולא מוסיפים לה את n.

לוקחים תת-קבוצה חוקית של המספרים בין 1 ל-n-2, לא מוסיפים לה את n-1, ומוסיפים לה את n.

לוקחים תת-קבוצה חוקית של המספרים בין 1 ל-n-3, לא מוסיפים לה את n-2, ומוסיפים לה את n-1 ואת n.
עליך לבדוק שכל תת-קבוצה חוקית של {1,2,3,...,n} נוצרת באופן זה בדיוק פעם אחת, ולמצוא את תנאי ההתחלה.