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

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

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)$ מונוטונית יורדת דומה מאד.