Home » Step Functions

Tag: Step Functions

Prove an inequality relating sums and integrals

Prove that

    \[ \sum_{k=1}^{n-1} f(k) \leq \int_1^n f(x) \, dx \leq \sum_{k=2}^n f(k) \]

where f is a nonnegative, increasing function defined for all x \geq 1.

Use this to deduce the inequalities

    \[ e n^n e^{-n} < n! < e n^{n+1} e^{-n} \]

by taking f(x) = \log x.


Proof. Since f(x) is increasing we know f([x]) \leq f(x) \leq f([x+1]) (where [x] denotes the greatest integer less than or equal to x) for all x \geq 1. Define step functions s and g by

    \[ s(x) = f([x]), \qquad t(x) = f([x+1]). \]

Then s and t are constant on the open subintervals of the partition

    \[ P = \{ 0,1,2, \ldots, n \}. \]

So,

    \begin{align*}  \int_1^n s(x) \, dx = \sum_{k=1}^{n-1} s_k (x_k - x_{k-1}) = \sum_{k=1}^{n-1} f(k) \\[9pt]  \int_1^n t(x) \, dx = \sum_{k=1}^{n-1} t_k (x_k - x_{k-1}) = \sum_{k=1}^{n-1} f(k+1) = \sum_{k=2}^n f(k). \end{align*}

Since f is integrable we must have

    \[ \int_1^n s(x) \, dx \leq \int_1^n f(x) \, dx \leq \int_1^n t(x) \, dx \]

for every pair of step functions s \leq f \leq t. Hence,

    \[ \sum_{k=1}^{n-1} f(k) \leq \int_1^n f(x) \, dx \leq \sum_{k=2}^n f(k). \qquad \blacksquare \]

Next, if we take f(x) = \log x (which is nonnegative and increasing on x \geq 1) we have

    \begin{align*}  &&\sum_{k=1}^{n-1} \log k \leq \int_1^n \log x \, dx \leq \sum_{k=2}^n \log k \\[9pt]  \implies && \log(n-1)! \leq n \log n - n + 1 \leq \log n! \\[9pt]  \implies && (n-1)! \leq e n^n e^{-n} \leq n!. \end{align*}

From this we then get two inequalities

    \[ n! \leq en^{n+1} e^{-n} \quad \text{and} \quad e n^n e^{-n} \leq n!. \]

Therefore,

    \[ en^n e^{-n} \leq n! \leq e n^{n+1} e^{-n}. \]

Prove some statements about integrals of bounded monotonic increasing functions

Consider a bounded, monotonic, real-valued function f on the interval [0,1]. The define sequences

    \[ s_n = \frac{1}{n} \sum_{k=0}^{n-1} f \left( \frac{n}{k} \right), \qquad t_n = \frac{1}{n} \sum_{k=1}^n f \left( \frac{k}{n} \right). \]

  1. Prove that

        \[ s_n \leq \int_0^1 f(x) \, dx \leq t_n \]

    and that

        \[ 0 \leq \int_0^1 f(x) \,dx - s_n \leq \frac{f(1) - f(0)}{n}. \]

  2. Prove that the two sequences \{ s_n \} and \{ t_n \} converge to \int_0^1 f(x) \, dx.
  3. State and prove a generalization of the above to interval [a,b].

  1. Proof.First, we define two step functions,

        \[ s(x) = f \left( \frac{[nx]}{n} \right), \qquad t(x) = f \left( \frac{[nx+1]}{n} \right) \]

    where [x] denotes the greatest integer less than or equal to x. Then we define a partition of [0,1],

        \[ P = \left\{ 0, \frac{1}{n}, \frac{2}{n}, \ldots, 1 \right\}. \]

    For any x_{k_1} \leq x < x_k we have

        \[ s(x) = f \left( \frac{k-1}{n} \right), \qquad t(x) = f \left( \frac{k}{n} \right). \]

    So, s(x) and t(x) are constant on the open subintervals of the partition P.
    Since f(x) is monotonically increasing and s(x) \leq f(x) \leq t(x) for all x (by the definition of s and t) we have

        \begin{align*}  &&\int_0^1 s(x) \, dx \leq \int_0^1 f(x) \, dx \leq \int_0^1 t(x) \, dx \\[9pt]  \implies && \sum_{k=0}^{n-1} s_k (x_k - x_{k-1} \leq \int_0^1 f(x) \, dx \leq \sum_{k=0}^{n-1} t_k (x_k - x_{k-1}) && (\text{Def step function integral}) \\[9pt]  \implies && \frac{1}{n} \sum_{k=0}^{n-1} f \left( \frac{k}{n} \right) \leq \int_0^1 f(x) \, dx \leq \frac{1}{n} \sum_{k=0}^{n-1} f \left( \frac{k+1}{n} \right) &&(x_k - x_{k-1} = \frac{1}{n} \forall k) \\[9pt]  \implies && \fract{1}{n} \sum_{k=0}^{n-1} f \left( \frac{k}{n} \right) \leq \int_0^1 f(x) \, dx \leq \frac{1}{n} \sum_{k=1}^nf \left( \frac{k}{n} \right) \\[9pt]  \implies && s_n \leq \int_0^1 f(x) \, dx \leq t_n && \text{for all } n \\[9pt]  \implies && 0 \leq \int_0^1 f(x) \, dx - s_n \leq t_n - s_n \\[9pt]  \implies && 0 \leq \int_0^1 f(x) \, dx - s_n \leq \frac{f(1) - f(0)}{n}. \qquad \blacksquare \end{align*}

  2. Proof. From part (a) we have

        \[ 0 \leq \int_0^1 f(x) \, dx - s_n \leq \frac{f(1) - f(0)}{n} \quad \implies \quad \lim_{n \to \infty} \left( \int_0^1 f(x) \, dx - s_n \right)= 0 \]

    since \lim_{n \to \infty} \frac{f(1)- f(0)}{n} = 0. Since \int_0^1 f(x) \, dx does not depend on n we have

        \[ \int_0^1 f(x) \, dx  - \lim_{n \to \infty} s_n = 0 \quad \implies \quad \lim_{n \to \infty} s_n = \int_0^1 f(x) \, dx. \]

    Therefore,

        \begin{align*}   && s_n \leq \int_0^1 f(x) \, dx \leq t_n \\[9pt]  \implies && s_n - t_n \leq \int_0^1 f(x) \, dx - t_n \leq 0 \\[9pt]  \implies && \frac{f(0)-f(1)}{n} \leq \int_0^1 f(x) \, dx - t_n \leq 0 \\[9pt]  \implies && \lim_{n \to \infty} \left( \int_0^1 f(x) \, dx - t_n \right) = 0 \\[9pt]  \implies && \lim_{n \to \infty} t_n = \int_0^1 f(x) \, dx. \qquad \blacksquare \end{align*}

  3. Claim: If f is a real-valued function that is monotonic increasing and bounded on the interval [a,b], then

        \[ \lim_{n \to \infty} s_n = \int_a^b f(x) \, dx, \qquad \text{and} \qquad \lim_{n \to \infty} t_n = \int_a^b f(x) \, dx \]

    for s_n and t_n defined as follows:

        \[ s_n = \frac{b-a}{n} \cdot sum_{k=0}^{n-1} f \left( a + k \frac{b-a}{n} \right), \qquad t_n = \frac{b-a}{n} \cdot \sum_{k=1}^n f \left( a + k \frac{b-a}{n} \right). \]

    Proof. Let

        \[ P = \left\{ a, a + \frac{b-a}{n}, a + \frac{2(b-a)}{n}, \ldots, a + \frac{n(b-a)}{n} = b \right\}  \]

    be a partition of the interval [a,b]. Then, define step functions s(x) and t(x) with s(x) = f(x_{k-1}) and t(x) = f(x_k) for x_{k-1} \leq x < x_k. By these definitions we have s(x) \leq f(x) \leq t(x) for all x \in [a,b] (since f is monotonic increasing). Since f is bounded and monotonic increasing it is integrable, and

        \begin{align*}  && \int_a^b s(x) \, dx \leq \int_a^b f(x) \, dx \leq \int_a^b t(x) \, dx \\[9pt]  \implies && \sum_{k=1}^n s_k (x_k - x_{k-1}) \leq \int_a^b f(x) \, dx \leq \sum_{k=1}^n t_k (x_k - x_{k-1}) \\[9pt]  \implies && \sum_{k=1}^n s_k \left( \frac{b-a}{n} \right) \leq \int_a^b f(x) \, dx \leq \sum_{k=1}^n t_k \left( \frac{b-a}{n} \right). \end{align*}

    And, since s_k = f(x_{k-1} = f \left( a + \frac{(k-1)(b-a)}{n} \right), and t_k = f(x_k) = f \left( a + \frac{k(b-a)}{n} \right) we have

        \begin{align*}  \implies && \sum_{k=1}^n f \left( a + \frac{(k-1)(b-a)}{n} \right) \left( \frac{b-a}{n} \right) \leq \int_a^b f(x) \, dx \leq \sum_{k=1}^n f \left( a + \frac{k(b-a)}{n} \right) \left( \frac{b-a}{n} \right) \\[9pt]  \implies && \left( \frac{b-a}{n} \right) \sum_{k=0}^{n-1} f \left( a+ \frac{k(b-a)}{n} \right) \leq \int_a^b f(x) \, dx \leq \left( \frac{b-a}{n} \right) \sum_{k=1}^n f \left( a+ \frac{k(b-a)}{n} \right). \qquad \blacksquare \end{align*}

Prove inequalities of the logarithm with respect to some series

Consider a partition P = \{ a_0, a_1, a_2, \ldots, a_n \} of the interval [1,x] for some x > 1.

  1. Find step functions that are constant on the open subintervals of P and integrate to derive the inequalities:

        \[ \sum_{k=1}^n \left( \frac{a_k - a_{k-1}}{a_k} \right) < \log x < \sum_{k=1}^n \left( \frac{a_k - a_{k-1}}{a_{k-1}} \right). \]

  2. Give a geometric interpretation of the inequalities in part (a).
  3. Find a particular partition P (i.e., choose particular values for a_0, a_1, \ldots, a_n) to establish the following inequalities for n > 1,

        \[ \sum_{k=2}^n \frac{1}{k} < \log n < \sum_{k=1}^{n-1} \frac{1}{k}. \]


  1. Proof. We define step function s and t by

        \begin{align*}  s(x) &= \frac{1}{a_k} & \text{for } x &\in [a_{k-1}, a_k ) \\  t(x) &= \frac{1}{a_{k-1}} & \text{for } x &\in [a_{k-1}, a_k ). \end{align*}

    Since \frac{1}{x} is strictly decreasing on \mathbb{R}_{>0}, we have

        \[ s(x) < \frac{1}{x} < t(x) \qquad \text{for all } x \in \mathbb{R}_{>0}. \]

    Therefore, using the definition of the integral of a step function as a sum,

        \begin{align*}  && \int_1^x s(u) \, du &< \int_1^x \frac{1}{u} \, du < \int_1^x t(u) \, du \\ \implies && \sum_{k=1} s_k (a_k - a_{k-1} ) &< \log x < \sum_{k=1}^n t_k (a_k - a_{k-1}) \\ \implies && \sum_{k=1}^n \left( \frac{a_k - a_{k-1}}{a_k} \right) &< \log x < \sum_{k=1}^n \left( \frac{a_k - a_{k-1}}{a_{k-1}} \right). \qquad \blacksquare \end{align*}

  2. Geometrically, these inequalities say that the area under the curve \frac{1}{x} lies between the step functions that take on the values \frac{1}{a_k} and \frac{1}{a_{k-1}} for each x \in [ a_{k-1}, a_k ).
  3. Proof. To establish these inequalities we pick the partition,

        \[ P = \{ 1, 2, 3, \ldots, n \} \qquad \text{for } n > 1. \]

    Then, applying part (a) we have

        \begin{align*}  && \sum_{k=1}^n \left( \frac{a_k - a_{k-1}}{a_k} \right) &< \log x < \sum_{k=1}^n \left( \frac{a_k - a_{k-1}}{a_{k-1}} \right) \\  \implies && \sum_{k=1}^n \frac{1}{a_k} &< \log n < \sum_{k=1}^n \frac{1}{a_{k-1}} &(\text{since } a_k - a_{k-1} = 1) \\  \implies && \sum_{k=2}^n \frac{1}{k} &< \log n < \sum_{k=1}^{n-1} \frac{1}{k}. \end{align*}

    The final line follows since a_0 = 1, a_1 = 2, \ldots so the sum on the left starts with \frac{1}{2} and the sum on the right only runs to \frac{1}{n-1}. These were the inequalities requested. \qquad \blacksquare

Prove the comparison theorem for integrals of step functions

For step functions s(x) < t(x) for every x \in [a,b] prove that

    \[ \int_a^b s(x) \, dx < \int_a^b t(x) \, dx. \]


Proof. Let P = \{ x_0, \ldots, x_n \} be a partition of [a,b] such that s(x) and t(x) are constant on the open subintervals of P (such a partition exists since we can take the common refinement of partitions on which s and t are constant on open subintervals). Then, assume s(x) = s_k, \ t(x) = t_k if x_{k-1} < x < x_k. From the definition of integrals of step functions, we have

    \[ \int_a^b s(x) \, dx = \sum_{k=1}^n s_k (x_k - x_{k-1}) \qquad \text{and} \qquad \int_a^b t(x) \, dx = \sum_{k=1}^n t_k (x_k - x_{k-1}). \]

Then, s_k < t_k (since s(x) < t(x) for every x \in [a,b]), which implies,

    \begin{align*}  &&\sum_{k=1}^n s_k (x_k - x_{k-1}) &< \sum_{k=1}^n t_k (x_k - x_{k-1}) \\ \implies && \int_a^b s(x) \, dx &< \int_a^b t(x) \, dx. \qquad \blacksquare \end{align*}

Prove the additive property of integrals of step functions

For s(x), t(x) step functions defined on an interval [a,b], prove

    \[ \int_a^b (s(x) + t(x)) \, dx = \int_a^b s(x) \, dx + \int_a^b t(x) \, dx. \]


Proof. Let P = \{ x_0, x_1, \ldots, x_n \} be a partition of [a,b] such that s(x)+t(x) is constant on the open subintervals of P (we know such a P exists since we can take the common refinement of the partition of [a,b] on which s(x) and t(x) individually are constant on open subintervals). Let s(x) + t(x) = s_k + t_k if x_{k-1} < x < x_k for k=1,2, \ldots, n. Then, working from the definition of the integral of a step function on an interval, we have

    \begin{align*}  \int_a^b (s(x)+t(x))\, dx &= \sum_{k=1}^n (s_k + t_k)(x_k - x_{k-1}) \\  &= \sum_{k=1}^n \left( s_k (x_k - x_{k-1}) + t_k (x_k - x_{k-1}) \right) \\  &= \sum_{k=1}^n s_k (x_k - x_{k-1}) + \sum_{k=1}^n t_k (x_k - x_{k-1}) \\  &= \int_a^b s(x) \, dx + \int_a^b t(x) \, dx. \qquad \blacksquare \end{align*}

Properties of another alternate definition of the integral of a step function

Suppose we defined the integral of a step function as:

    \[ \int_a^b s(x) \, dx = \sum_{k=1}^n s_k \cdot (x_k^2 - x_{k-1}^2). \]

Which of the following properties of the integral would still hold:

  1. \displaystyle{\int_a^b s + \int_b^c s = \int_a^c s}.
  2. \displaystyle{\int_a^b (s+t) = \int_a^b s + \int_a^b t}.
  3. \displaystyle{\int_a^b c \cdot s = c \cdot \int_a^b s}.
  4. \displaystyle{\int_{a+c}^{b+c} s(x) \, dx = \int_a^b s(x+c) \, dx}.
  5. If s(x) < t(x) for all x \in [a,b], then \displaystyle{ \int_a^b s < \int_a^b < t}.

  1. True.
    Proof. Let P = \{ x_0, \ldots, x_m \} be a partition of [a,c] and P_2 = \{ y_0, \ldots, y_n \} be partition of [b,c] such that s(x) is constant on the open subintervals of P_1 and P_2. Then, let P = P_1 \cup P_2 = \{ x_0, \ldots, x_m, x_{m+1}, \ldots, x_{m+n} \}, where x_m = y_0, x_{m+1} = y_1, \ldots, x_{m+n} = y_n, so P is a partition of [a,c] and s(x) is constant on the open subintervals of P. Then,

        \begin{align*}  \int_a^b s(x) \, dx + \int_b^c s(x) \, dx &= \sum_{k=1}^m s_k (x_k^2 - x_{k-1}^2) + \sum_{k=1}^n s_k (y_k^2 - y_{k-1}^2) & (\text{``def." of } \int_a^b s)\\  &= \sum_{k=1}^m s_k (x_k^2 - x_{k-1}^2) + \sum_{k=m+1}^{m+n} s_k (x_k^2 - x_{k-1}^2) \\  &= \sum_{k=1}^{m+n} s_k (x_k^2 - x_{k-1}^2) \\  &= \int_a^c s(x) \, dx. \qquad \blacksquare \end{align*}

  2. True.
    Proof. Let P = \{ x_0, \ldots, x_n \} be partition of [a,b] such that s(x) + t(x) is constant on the open subintervals of P. (We know such a partition exists since we can take the common refinement of the partitions of [a,b] on which s and t individually are constant.) Assume s(x) + t(x) = s_k + t_k if x_{k-1} < x < x_k for k = 1,2, \ldots, n. Then,

        \begin{align*}  \int_a^b (s(x) + t(x)) \, dx &= \sum_{k=1}^n (s_k + t_k)(x_k^2 - x_{k-1}^2) \\  &= \sum_{k=1}^n \left( s_k (x_k^2 - x_{k-1}^2) + t_k (x_k^2 - x_{k-1}^2) \right) \\  &= \sum_{k=1}^n s_k (x_k^2 - x_{k-1}^2) + \sum_{k=1}^n t_k (x_k^2 - x_{k-1}^2) \\  &= \int_a^b s(x) \, dx + \int_a^b t(x) \, dx. \qquad \blacksquare \end{align*}

  3. True.
    Proof. Let P = \{ x_0, \ldots, x_n \} be a partition of [a,b] such that s is constant on the open subintervals of P. Assume s(x) = s_k if x_{k-1} < x < x_k for k = 1, \ldots, n. Then c \cdot s(x) = c \cdot s_k if x_{k-1} < x < x_k so using our alternative definition of the integral we have,

        \begin{align*}  \int_a^b s(x) \, dx &= \sum_{k=1}^n c \cdot s_k \cdot (x_k^2 - x_{k-1}^2) \\  &= c \cdot \sum_{k=1}^n s_k (x_k^2 - x_{k-1}^2) \\  &= c \cdot \int_a^b s(x) \, dx. \qquad \blacksquare \end{align*}

  4. False. Since s((x_k + c)^2 - (x_{k-1} +c)^2) \neq (s+c)(x_k^2 - x_{k-1}^2). In particular, a counterexample is given by letting s(x) = 1 for all x \in [1,2] and let c = 1. Then,

        \begin{align*}   \int_{0+1}^{1+1} s(x) \, dx &= 1 \cdot (2^2 - 1^2) = 3 \\   \int_0^1 s(x+1) \, dx &= 1 \cdot (1^2 - 0^2) = 1.  \end{align*}

  5. False.
    A counterexample is given by considering s(x) = 0 and t(x) = 1 on the interval [-1,0]. Then, s < t on the interval, but

        \[ \int_{-1}^0 s(x) \, dx = 0 \not< \int_{-1}^0 t(x) \, dx = 1 \cdot (0^2 - (-1)^2) = -1. \]

Properties of an alternate definition of the integral of a step function

Consider if we chose the following definition for the definite integral of a step function:

    \[ \int_a^b s(x) \, dx = \sum_{k=1}^n s_k^3 \cdot (x_k - x_{k-1}). \]

Which of the following properties (all valid for the actual definition) would remain valid under this new definition:

  1. \displaystyle{\int_a^b s + \int_b^c s = \int_a^c s}.
  2. \displaystyle{\int_a^b (s+t) = \int_a^b s + \int_a^b t}.
  3. \displaystyle{\int_a^b c \cdot s = c \cdot \int_a^b s}.
  4. \displaystyle{\int_{a+c}^{b+c} s(x) \, dx = \int_a^b s(x+c) \, dx}.
  5. If s(x) < t(x) for all x \in [a,b], then \displaystyle{ \int_a^b s < \int_a^b < t}.

  1. True.
    Proof. Let P_1 = \{ x_0, \ldots, x_m \} be a partition of [a,c] and P_2 = \{ y_0, \ldots, y_n \} be a partition of [c,b] such that s(x) is constant on the open subintervals of P_1 and P_2. Then, let P = P_1 \cup P_2 = \{ x_0, \ldots, x_m, x_{m+1}, \ldots, x_{m+n} \}, where x_m = y_0, x_{m+1} = x_0, \ldots, x_{m+n} = y_n, so P is a partition of [a,b] and s(x) is constant on the open subintervals of P. Then,

        \begin{align*}  \int_a^c s(x) \, dx + \int_c^b s(x) \, dx &= \sum_{k=1}^m s_k^3 (x_k - x_{k-1}) + \sum_{k=1}^n s_k^3 (y_k - y_{k-1}) & (\text{``def." of } \int_a^b s)\\  &= \sum_{k=1}^m s_k^3 (x_k - x_{k-1}) + \sum_{k=m+1}^{n+m} s_k^3 (x_k - x_{k-1}) \\  &= \sum_{k=1}^{m+n} s_k^3 (x_k - x_{k-1}) \\  &= \int_a^b s(x) \, dx. \qquad \blacksquare \end{align*}

  2. False.
    Counterexample: Let s(x) = t(x) = 1 for all x \in [0,1]. Then,

        \[ \int_0^1 (s(x) + t(x)) \, dx = 8 \]

    while

        \[ \int_0^1 s(x) \, dx + \int_0^1 t(x) \, dx = 1 + 1 = 2. \]

    Hence, this property does not hold. (More generally, since (s+t)^3 \neq s^3 + t^3.)

  3. False. Again, this is because (cs)^3 \neq c(s^3). A specific counterexample is given.
    Counterexample: Let s(x) = 1 for all x \in [0,1] and let c = 2. Then,

        \[ \int_0^1 c \cdot s(x) \, dx = (2)^3 = 8, \]

    while,

        \[ c \cdot \int_0^1 s(x) \, dx = 2 \cdot 1 = 2. \]

  4. True.
    Proof. Let P =\{ x_0, \ldots, x_n \} be a partition of [a,b] such that s(x) = s_k on the kth open subinterval of P. Then,

        \[ P = \{ x_0 + c, x_1 + c, \ldots, x_n + c \} \]

    is a partition of [a+c, b+c] and s(x-c) = s_k on x_{k-1} + c < x < x_k + c. So,

        \[ \int_a^b s(x) \, dx = \sum_{k=1}^n s_k^3 (x_k - x_{k-1}) \qquad \text{and} \qquad \int_{a+c}^{b+c} s(x-c) \, dx = \sum_{k=1}^n s_k^3 (x_k - x_{k-1}). \]

    Thus, indeed we have

        \[ \int_a^b s(x) \, dx = \int_{a+c}^{b+c} s(x-c) \, dx. \qquad \blacksquare \]

  5. True.
    Proof. Since s(x) < t(x) implies s(x)^3 < t(x)^3, the result follows immediately. \qquad \blacksquare