דף הבית
אקראי
כניסה לחשבון
הגדרות
תרומה לוויקיספר
אודות ויקיספר
הבהרות משפטיות
חיפוש
מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/סדרי גדילה/תרגילים/חסמי אינטגרלים/תשובה
שפה
מעקב
עריכה
<
מבני נתונים ואלגוריתמים - מחברת קורס
|
אלגוריתמים
|
סדרי גדילה
|
תרגילים
זו למעשה שאלה מחדו"א:
היות ש
f
(
n
)
{\displaystyle \displaystyle f(n)}
מונוטונית לא יורדת, אז:
∫
m
−
1
n
f
(
x
)
d
x
=
∑
i
=
m
−
1
n
−
1
∫
i
i
+
1
f
(
x
)
d
x
≤
∑
i
=
m
−
1
n
−
1
∫
i
i
+
1
f
(
i
+
1
)
d
x
=
∑
i
=
m
n
[
f
(
i
)
]
{\displaystyle \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)]}
∫
m
n
+
1
f
(
x
)
d
x
=
∑
i
=
m
n
∫
i
i
+
1
f
(
x
)
d
x
≥
∑
i
=
m
n
∫
i
i
+
1
f
(
i
)
d
x
=
∑
i
=
m
n
[
f
(
i
)
]
{\displaystyle \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)]}
כפי שנכתב בשאלה, המקרה שבו
f
(
n
)
{\displaystyle \displaystyle f(n)}
מונוטונית יורדת דומה מאד.
![{\displaystyle \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)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/94698d1724faf0f336b4f428ca590fc9d6be3c02)
![{\displaystyle \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)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c379a6f03b255ee999ee56f7cb9ad51a848f244a)