אינדוקציה

[globus1988]

אינדוקציה

שלום לכולם,
אני מצרף כאן 2 תרגילים באינדוקציה שלא הצלחתי להוכיח. אני די בטוח שצריך לנצל בשניהם את ההנחה ש-n גדול\שווה 2, אבל לא הצלחתי להגיע לפתרון.
תוכלו בבקשה לעזור לי?
תוכלו לוותר על הניסוח הפורמאלי של האינדוקציה כדי לגעת בעיקר והוא צעד האינדוקציה.
תודה מראש!

 

[אורי769]

הדרכה

בשני התרגילים האלה אתה נדרש לעשות אינדוקציה רגילה. האתגר כאן הוא לדעת לעבוד עם אי-שויונים באופן אלגברי. כלומר, להעריך ביטוי מלמעלה. זו טכניקה שלא נלמדת בתיכון ולכן קשה לסטודנטים בראשית דרכם.
בשני התרגילים יש לך איזשהו סכום =< (f(n.
נסה להתחיל בלחשב כמה זה (f(n+1) - f(n. אח"כ תחשב כמה תוספת יש לסכום בצעד האינדוקציה. מכאן נשאר לך להוכיח שהראשון גדול מהשני. נסה ואם תתקע אני אנסה לעזור עם הטכניקה.