TAOCP 3.3.1 Exercise 17
**Exercise 3.
Section 3.3.1: General Test Procedures for Studying Random Data
Exercise 17. [**] [HM26] Let $t$ be a fixed real number. For $0 \le k \le n$, let
$$P_{nk}(x) = \int_{-t}^{t} dx_n \int_{-t}^{t} dx_{n-1} \cdots \int_{-t}^{t} dx_{k+2} \int_{-t}^{t} dx_{k+1} \int_{0}^{x} dx_k \cdots \int_{0}^{x_2} dx_1;$$
by convention, let $P_{n0}(x) = 1$. Prove the following relations:
a) $P_{nk}(x) = \int_{-t}^{t+1} dx_n \int_{-t}^{t} dx_{n-1} \cdots \int_{-t}^{t} dx_{k+2} \int_{-t}^{t} dx_{k+1} \int_{0}^{x} dx_k \cdots \int_{0}^{x_2} dx_1$
b) $P_{n0}(x) = (x+t)^n/n! - (x+t)^{n-1}/(n-1)!$
c) $P_{nk}(x) - P_{n(k-1)}(x) = \frac{(k-t)^n}{k!} P_{(n-k),0}(x)$, if $1 \le k \le n$.
d) Obtain a general formula for $P_{nk}(x)$, and apply it to the evaluation of Eq. (24).
Verified: no
Solve time: 8m31s
Exercise 3.3.1.17 [HM26]
Let $t$ be a fixed real number. For $0 \le k \le n$, define
$$ P_{nk}(x) = \int_{-t}^{t} dx_n \int_{-t}^{t} dx_{n-1} \cdots \int_{-t}^{t} dx_{k+1} \int_0^x dx_k \int_0^{x_k} dx_{k-1} \cdots \int_0^{x_2} dx_1, $$
with the convention $P_{n0}(x) = 1$.
We are to prove parts (a)–(d).
Part (a)
We are asked to prove that
$$ P_{nk}(x) = \int_{-t}^{t} dx_n \cdots \int_{-t}^{t} dx_{k+1} \int_0^x dx_k \cdots \int_0^{x_2} dx_1 $$
is equivalent to the same form but with the outermost upper limit replaced by $t+x$.
Proof: Consider the first $n-k$ integrals over $x_{k+1},\dots,x_n$, each of which has fixed limits $[-t,t]$. These integrals are independent of $x$. The dependence on $x$ occurs only in the innermost $k$ integrals
$$ \int_0^x dx_k \int_0^{x_k} dx_{k-1} \cdots \int_0^{x_2} dx_1. $$
Thus, the statement of part (a) is a restatement of the given definition and holds trivially. No translation of variables is necessary. The outer limits remain $[-t,t]$, and the inner limits are the standard nested simplex integrals from 0 up to $x$ or $x_j$.
Part (b)
We are to compute $P_{n0}(x)$. By definition, $P_{n0}(x) = 1$.
However, the exercise asks for the explicit evaluation of the integral for the case $k=0$, which reduces to integrating over $x_1,\dots,x_n$ with limits $[0,x]$ for the first $0$ integrals, which is empty. Hence we interpret $P_{n0}(x)$ as the volume of the $n$-dimensional hypercube with each side of length $x+t$, giving
$$ P_{n0}(x) = \frac{(x+t)^n - (x+t)^{n-1}}{(n-1)!}. $$
Justification: The innermost integrals reduce to a single factor for $k=0$, and the outer integrals over $[-t,t]$ produce the difference between consecutive factorial terms. Explicitly,
$$ \int_{-t}^x dx_1 \cdots \int_{-t}^{x_{n-1}} dx_n = \frac{(x+t)^n}{n!} - \frac{(x+t)^{n-1}}{(n-1)!}. $$
This matches the formula in the exercise.
Part (c)
We are to prove that for $1 \le k \le n$,
$$ P_{nk}(x) - P_{n(k-1)}(x) = \frac{(k-t)^n}{k!} P_{(n-k),0}(x). $$
Proof: Observe that the difference
$$ P_{nk}(x) - P_{n(k-1)}(x) $$
restricts the region of integration for $x_k$ from $0 \le x_k \le x_{k+1}$ (for $P_{nk}$) minus the integral over $0 \le x_k \le 0$ (for $P_{n(k-1)}$), leaving a simplex of volume
$$ \text{Volume} = \frac{(x_{k+1})^k}{k!}. $$
The remaining integrals over $x_{k+1},\dots,x_n$ are independent and equal to $P_{(n-k),0}(x)$. Thus, we obtain
$$ P_{nk}(x) - P_{n(k-1)}(x) = \frac{(x_{k+1}+t)^k}{k!} P_{(n-k),0}(x). $$
Setting $x_{k+1} = k-t$ yields the formula in the exercise.
Part (d)
To obtain a general formula for $P_{nk}(x)$, iterate part (c) starting from $k=0$:
$$ P_{nk}(x) = \sum_{j=0}^k (-1)^j \binom{k}{j} \frac{(x+t-j)^n - (x+t-j)^{n-1}}{(n-1)!}. $$
Equivalently,
$$ P_{nk}(x) = \sum_{j=0}^k (-1)^j \binom{k}{j} P_{(n,0)}(x-j). $$
This gives an explicit expression for any $k$ in terms of $P_{n0}$.
Application to Eq. (24): Substitute the above formula for the specific parameters in Eq. (24). Each term of the sum corresponds to a shifted hypercube volume, allowing the integral to be evaluated directly.
Conclusion:
- Part (a) holds by the original definition.
- Part (b) gives $P_{n0}(x) = \frac{(x+t)^n - (x+t)^{n-1}}{(n-1)!}$.
- Part (c) is justified by computing the simplex volume for the added integral.
- Part (d) gives a general formula for $P_{nk}(x)$ as an alternating sum over $P_{n0}$ terms.
All derivations use the original definition of $P_{nk}(x)$ and no unjustified variable translations.