חוקר נוסחאות רקורסיה
הציגו במדויק את איברי הרקורסיה, ובמקרה של רקורסיה ליניארית עם מקדמים קבועים מצאו צורה סגורה מתוך השורשים האופייניים. אפשר גם לבדוק את ההשערה שלכם מול כל איבר שחושב.
הקלט מוגבל ל־1,000 תווים ולסדר 10; פולינומי הכפייה יכולים להיות ממעלה 3 ובעלי 1 עד 200 איברים; ערכים מדויקים יכולים לגדול עד 1,024 ספרות. הכול מחושב במכשירכם בתהליך רקע, עם מגבלת זמן של 15 שניות. ניתן להוריד דוח JSON וקובץ CSV של האיברים. כתבו תחילה את הרקורסיה, ואז את הערכים ההתחלתיים כשהם מופרדים בפסיקים או בשורות חדשות. עד 1,000 תווים. בדקו את ההגדרות לפני ההרצה.
התוצאה שלכם
חוקר נוסחאות רקורסיה
- הקלידו את הרקורסיה ואת הערכים ההתחלתיים, כגון a(n) = a(n-1) + a(n-2), a(0) = 0, a(1) = 1.
- אפשר להוסיף השערה, כגון guess: a(n) = 2^n - 1, ולבחור כמה איברים להציג.
- הריצו את החוקר וקראו את האיברים, השורשים האופייניים והצורה הסגורה.
- הורידו את דוח JSON או את קובץ ה־CSV של האיברים.
מה צפוי לקרות
הקלט מוגבל ל־1,000 תווים ולסדר 10; דרגת פולינומי הכפייה היא לכל היותר 3. ניתן לחשב 1 עד 200 איברים. ערכים מדויקים יכולים לגדול עד 1,024 ספרות. הכול מחושב במכשירכם בתהליך רקע, עם מגבלת זמן של 15 שניות. ניתן להוריד דוח JSON וקובץ CSV של האיברים.
צורות סגורות
עבור a(n) = c1 a(n-1) + ... + ck a(n-k) + f(n), כאשר f פולינום, הפולינום האופייני מפורק במדויק. כל שורש r בריבוי m תורם איברים r^n, n r^n וכן הלאה; פתרון פרטי פולינומי מטפל ב־f, והקבועים נקבעים מהערכים ההתחלתיים. נתמכים שורשים רציונליים ושורשים מהצורה p + q*sqrt(d). השיטה: Rosen, Discrete Mathematics and Its Applications, מהדורה 8, סעיף 8.2 (2019).
בדיקות
הצורה הסגורה מחושבת במדויק בכל איבר שחושב וחייבת להתאים לו. השערה מושווית איבר אחר איבר; התאמה במספר סופי של איברים היא ראיה, לא הוכחה.
רקורסיות אחרות
רקורסיות לא־ליניאריות כגון a(n) = n*a(n-1) מפותחות במדויק, אך לא מתקבלת עבורן צורה סגורה. שורשים אופייניים מרוכבים ושורשים של גורמים ממעלה שלישית ומעלה מסומנים כלא נתמכים במקום לנחש אותם.