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

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

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