מבני נתונים ואלגוריתמים - מחברת קורס/נספחים/מתמטיקה/תרגילים

חסמי אינטגרלים

שאלה

אנא הוכח אחד מחסמי האינטגרלים הבאים (שתי ההוכחות דומות מאד זו לזו):

1. אם $\displaystyle f(n)$ מונוטונית לא יורדת, אז $\displaystyle \int _{m-1}^{n}f(x)dx\leq \sum _{i=m}^{n}[f(i)]\leq \int _{m}^{n+1}f(x)dx$
2. אם $\displaystyle f(n)$ מונוטונית לא עולה, אז $\displaystyle \int _{m}^{n+1}f(x)dx\leq \sum _{i=m}^{n}[f(i)]\leq \int _{m-1}^{n}f(x)dx$

תשובה

זו למעשה שאלה מחדו"א:

1. היות ש$\displaystyle f(n)$ מונוטונית לא יורדת, אז:
   • $\displaystyle \int _{m-1}^{n}f(x)dx=\sum _{i=m-1}^{n-1}\int _{i}^{i+1}f(x)dx\leq \sum _{i=m-1}^{n-1}\int _{i}^{i+1}f(i+1)dx=\sum _{i=m}^{n}[f(i)]$
   • $\displaystyle \int _{m}^{n+1}f(x)dx=\sum _{i=m}^{n}\int _{i}^{i+1}f(x)dx\geq \sum _{i=m}^{n}\int _{i}^{i+1}f(i)dx=\sum _{i=m}^{n}[f(i)]$
2. כפי שנכתב בשאלה, המקרה שבו $\displaystyle f(n)$ מונוטונית יורדת דומה מאד.