Skip to main content
Engineering LibreTexts

13.3: Approximating Sums

  • Page ID
    48388
    • Eric Lehman, F. Thomson Leighton, & Alberty R. Meyer
    • Google and Massachusetts Institute of Technology via MIT OpenCourseWare
    \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    Unfortunately, it is not always possible to find a closed-form expression for a sum. For example, no closed form is known for

    \[\nonumber S = \sum_{i = 1}^{n} \sqrt{i}.\]

    In such cases, we need to resort to approximations for \(S\) if we want to have a closed form. The good news is that there is a general method to find closed-form upper and lower bounds that works well for many sums. Even better, the method is simple and easy to remember. It works by replacing the sum by an integral and then adding either the first or last term in the sum.

    Definition \(\PageIndex{1}\)

    A function \(f : \mathbb{R}^+ \rightarrow \mathbb{R}^+\) is strictly increasing when

    \[\nonumber x < y \text{ IMPLIES } f(x) < f(y),\]

    and it is weakly increasing 3 when

    \[\nonumber x < y \text{ IMPLIES } f(x) \leq f(y).\]

    Similarly, \(f\) is strictly increasing when

    \[\nonumber x < y \text{ IMPLIES } f(x) > f(y),\]

    and it is weakly decreasing 4 when

    \[\nonumber x < y \text{ IMPLIES } f(x) \geq f(y).\]

    For example, \(2^x\) and \(\sqrt{x}\) are strictly increasing functions, while \(\text{max}\{x, 2\}\) and \(\lceil x\rceil\) are weakly increasing functions. The functions \(1/x\) and \(2^{-x}\) are strictly decreasing, while \(\text{min}\{1/x, 1/2\}\) and \(\lfloor 1/x \rfloor\) are weakly decreasing.

    Theorem \(\PageIndex{1}\)

    Let \(f : \mathbb{R}^+ \rightarrow \mathbb{R}^+\) be a weakly increasing function. Define

    \[S ::= \sum_{i=1}^{n}f(i) \label{13.3.1}\]

    and

    \[I ::= \int_{1}^{n} f(x) dx.\nonumber\]

    Then

    \[I + f(1) \leq S \leq I + f(n). \label{13.3.2}\]

    Similarly, if \(f\) is a weakly decreasing, then

    \[\nonumber I + f(n) \leq S \leq I + f(1).\]

    Proof

    Suppose \(f : \mathbb{R}^+ \rightarrow \mathbb{R}^+\) is weakly increasing. The value of the sum \(S\) in \ref{13.3.1} is the sum of the areas of \(n\) unit-width rectangles of heights \(f(1), f(2), \ldots, f(n)\). This area of these rectangles is shown shaded in Figure 13.1.

    The value of

    \[\nonumber I = \int_{1}^{n} f(x) dx\]

    is the shaded area under the curve of \(f(x)\) from 1 to \(n\) shown in Figure 13.2.

    Comparing the shaded regions in Figures 13.1 and 13.2 shows that \(S\) is at least \(I\) plus the area of the leftmost rectangle. Hence,

    \[S \geq I + f(1)\]

    This is the lower bound for S given in \ref{13.3.2}.

    To derive the upper bound for \(S\) given in \ref{13.3.2}, we shift the curve of \(f(x)\) from 1 to \(n\) one unit to the left as shown in Figure 13.3.

    Comparing the shaded regions in Figures 13.1 and 13.3 shows that \(S\) is at most \(I\) plus the area of the rightmost rectangle. That is,

    \[\nonumber S \leq I + f(n)\]

    which is the upper bound for S given in \ref{13.3.2}.

    The very similar argument for the weakly decreasing case is left to Problem 13.10. \(\quad \blacksquare\)

    clipboard_eda5ada839d8e9bdb771587ce5aa7eb6d.png
    Figure 13.1 The area of the \(i\)th rectangle is \(f(i)\). The shaded region has area \(\sum_{i=1}^{n}f(i)\).
    clipboard_e523d214e5c568960785754523872f8b3.png
    Figure 13.2 The shaded area under the curve of \(f(x)\) from 1 to \(n\) (shown in bold) is \(I = \int_{1}^{n}f(x)dx\).
    clipboard_edf687afccf520922580c4d80ce69eb30.png
    Figure 13.3 This curve is the same as the curve in Figure 13.2 shifted left by 1.

    Theorem 13.3.2 provides good bounds for most sums. At worst, the bounds will be off by the largest term in the sum. For example, we can use Theorem 13.3.2 to bound the sum

    \[\nonumber S = \sum_{i=1}^{n} \sqrt{i}\]

    as follows.

    We begin by computing

    \[\begin{aligned} I &= \int_{1}^{n} \sqrt{x} dx \\ &= \dfrac{x^{3/2}}{3/2}\bigg|_{1}^{n} \\ &= \dfrac{2}{3}(n^{3/2} - 1). \end{aligned}\]

    We then apply Theorem 13.3.2 to conclude that

    \[\nonumber \dfrac{2}{3}(n^{3/2} - 1) + 1 \leq S \leq \dfrac{2}{3}(n^{3/2} - 1) + \sqrt{n}\]

    and thus that

    \[\nonumber \dfrac{2}{3}n^{3/2} + \dfrac{1}{3} \leq S \leq \dfrac{2}{3}n^{3/2} + \sqrt{n} - \dfrac{2}{3}.\]

    In other words, the sum is very close to \(\dfrac{2}{3}n^{3/2}\). We’ll define several ways that one thing can be “very close to” something else at the end of this chapter.

    As a first application of Theorem 13.3.2, we explain in the next section how it helps in resolving a classic paradox in structural engineering.

    3Weakly increasing functions are usually called nondecreasing functions. We will avoid this terminology to prevent confusion between being a nondecreasing function and the much weaker property of not being a decreasing function.

    4Weakly decreasing functions are usually called nonincreasing.


    This page titled 13.3: Approximating Sums is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Eric Lehman, F. Thomson Leighton, & Alberty R. Meyer (MIT OpenCourseWare) .

    • Was this article helpful?