Tag: Partitions

Prove an inequality relating sums and integrals

by RoRi

March 4, 2016

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

by RoRi

February 29, 2016

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).$

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}.$
Prove that the two sequences $\{ s_n \}$ and $\{ t_n \}$ converge to $\int_0^1 f(x) \, dx$ .
State and prove a generalization of the above to interval $[a,b]$ .

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*}$
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*}$
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

by RoRi

November 6, 2015

Consider a partition $P = \{ a_0, a_1, a_2, \ldots, a_n \}$ of the interval $[1,x]$ for some $x > 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).$
Give a geometric interpretation of the inequalities in part (a).
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}.$

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*}$
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 )$ .
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 additive property of integrals of step functions

by RoRi

July 20, 2015

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*}$

More integrals of step functions

by RoRi

July 18, 2015

Compute
$\int_0^9 \left[ \sqrt{t} \right] \, dt.$
For $n \in \mathbb{Z}_{>0}$ prove
$\int_0^n \left[ \sqrt{t} \right] \, dt = \frac{n(n-1)(4n+1)}{6}.$

We compute,
$\int_0^9 \left[ \sqrt{t} \right] \, dt = (0 \cdot 1) + (1 \cdot (4-1)) + (2 \cdot (9-4)) = 13.$
Proof. Let $P = \{ 0,1,4,9, \ldots, n^2 \}$ . Then $P$ is a partition of $[0,n^2]$ and $\left[ \sqrt{t} \right]$ is constant on the open subintervals of $P$ . Further, for $(k-1)^2 < t < k^2$ we have $\left[ \sqrt{t} \right] = (k-1)$ . Thus, we have (using this exercise and this exercise to evaluate some of the sums),
$\begin{align*} \int_0^{n^2} \left[ \sqrt{t} \right] \, dt &= \sum_{k=1}^n (k-1) \cdot (k^2 - (k-1)^2) \\ &= \sum_{k=1}^n (k-1) \cdot (2k-1) \\ &= \sum_{k=1}^n (2k^2 - 3k + 1 ) \\ &= 2 \sum_{k=1}^n k^2 - 3 \sum_{k=1}^n k + \sum_{k=1}^n 1 \\ &= \frac{2n^3}{3} + n^2 + \frac{n}{3} - \frac{3n^2}{2} - \frac{3n}{2} + n \\ &= \frac{4n^3 - 3n^2 - n}{6} \\ &= \frac{n(n-1)(4n+1)}{6}. \qquad \blacksquare \end{align*}$

Find some formulas for the integral of the step function [t]^2

by RoRi

July 18, 2015

For $n \in \mathbb{Z}_{>0}$ , prove
$\int_0^n [t]^2 \, dt = \frac{n(n-1)(2n-1)}{6}.$
For $x \in \mathbb{R}$ , with $x \geq 0$ , define
$f(x) = \int_0^x [t]^2 \, dt.$

Draw the graph of $f$ on the interval $[0,3]$ .
Find all real $x > 0$ such that
$\int_0^x [t]^2 \, dt = 2(x-1).$

Proof. Let $P = \{ 0,1, \ldots, n \}$ . Then $P$ is a partition of $[0,n]$ and $[t]^2$ is constant on the open subintervals of $P$ . Further, $[t]^2 = (k-1)^2$ for $k-1 < t < k$ . So,
$\begin{align*} \int_0^n [t]^2 \, dt &= \sum_{k=1}^n (k-1)^2 \cdot (k-(k-1)) \\ &= \sum_{k=1}^n (k-1)^2 \\ &= \sum_{k=0}^{n-1} k^2 \\ &= \frac{n^3}{3} - \frac{n^2}{2} + \frac{n}{6} \\ &= \frac{n(n-1)(2n-1)}{6}. \end{align*}$

The second to last line follows from this exercise (I.4.7, #6) $. \qquad \blacksquare$
The graph is:
By inspection, we have, $x = 1, \frac{5}{2}$ .

Compute integrals of some more step functions

by RoRi

July 18, 2015

Prove
$\int_0^2 [t^2] \, dt = 5 - \sqrt{2} - \sqrt{3}.$
Compute
$\int_{-3}^3 [t^2] dt.$

Proof. Let $P = \{ 0, 1, \sqrt{2}, \sqrt{3}, 2 \}$ be a partition of $[0,2]$ . Then $[t^2]$ is constant on the open subintervals of $P$ , so,
$\begin{align*} \int_0^2 [t^2] \, dt &= \sum_{k=1}^5 s_k \cdot (x_k - x_{k-1}) \\ &= (0 \cdot 1) + (1)(\sqrt{2}-1) + (2)(\sqrt{3}- \sqrt{2}) + (3)(2 - \sqrt{3}) \\ &= 5 - \sqrt{2} - \sqrt{3}. \qquad \blacksquare \end{align*}$
We compute,
$\begin{align*} \int_{-3}^3 [t^2] \, dt &= 2 \cdot \int_0^3 [t^2] \, dt \\ &= 2 \cdot \left( \int_0^2 [t^2] \, dt + \int_2^3 [t^2] \, dt \right) \\ &= 2 \cdot \left( 5 - \sqrt{2} - \sqrt{3} + 4(\sqrt{5}-2) + 5(\sqrt{6} - \sqrt{5}) + 6(\sqrt{7}-\sqrt{6}) \right.\\ & \qquad \quad \left.+ 7(\sqrt{8} - \sqrt{7}) + 8(3 - \sqrt{8}) \right) \\ &= 2 (21 - 3\sqrt{2} - \sqrt{3} - \sqrt{5} - \sqrt{6} - \sqrt{7}). \end{align*}$

Compute some integrals of step functions

by RoRi

July 18, 2015

Let $n \in \mathbb{Z}_{>0}$ , prove
$\int_0^n [t] \, dt = \frac{n(n-1)}{2}.$
Let $x \in \mathbb{R}_{>0}$ , and define
$f(x) = \int_0^x [t] \, dt.$

Draw the graph of $f$ for $0 \leq x \leq 4$ .

Proof. Let $P = \{ 0,1,2, \ldots, n \}$ be a partition of $[0,n]$ . Then, by the definition of the greatest integer function, $[t]$ is constant on the open subintervals of $P$ , so
$\begin{align*} \int_0^n [t] \, dt &= \sum_{k=1}^n (k-1)(k-(k-1)) & (s_k = k-1 \text{ since } [t]=k-1 \text{ if } k-1 < t < k)\\ &= \sum_{k=1}^n (k-1) \\ &= \sum_{k=0}^{n-1} k \\ &= \frac{n(n-1)}{2}. \end{align*}$

The final equality follows from here (I.4.7, #5) $. \qquad \blacksquare$
The graph is:

Draw the graphs of some functions

by RoRi

July 16, 2015

Draw the graphs of the functions defined below on the interval $[-2,2]$ , and if it is a step function find a partition $P$ such that the function is constant on the open subintervals of $P$ .

$f(x) = x + [x]$ .
$f(x) = x - [x]$ .
$f(x) = [-x]$ .
$f(x) = 2[x]$ .
$f(x) = \left[x+\frac{1}{2} \right]$ .
$f(x) = [x] + \left[ x+ \frac{1}{2} \right]$ .

This is not a step function. The graph is below.
This is not a step function. The graph is below.
This is a step function and it is constant on the open subintervals of the partition, $P = \{ -2,-1,0,1,2 \}$ . The graph is below.
This is a step function and it is constant on the open subintervals of the partition, $P = \{ -2,-1,0,1,2 \}$ . The graph is below.
This is a step function and it is constant on the open subintervals of the partition, $P = \left\{ -2,-\frac{3}{2},-\frac{1}{2},\frac{1}{2},\frac{3}{2},2 \right\}$ . The graph is below.
This is a step function and it is constant on the open subintervals of the partition, $P = \left\{ -2,-\frac{3}{2},-1,-\frac{1}{2},0,\frac{1}{2},1,\frac{3}{2},2 \right\}$ . The graph is below.