brain

tamnd's digital brain — notes, problems, research

41641 notes

TAOCP 1.2.3 Exercise 31

Let T = \sum_{1 \le j < k \le n} (u_j - u_k)(v_j - v_k).

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.3 Exercise 32

For each integer $j$ with $1 \le j \le n$, define S_j = \sum_{i=1}^m a_{ij}.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.3 Exercise 33

Let $x_1, x_2, \ldots, x_n$ be distinct numbers and define $P(x)=\prod_{k=1}^n (x-x_k).$ Then for each $j$, $P'(x_j)=\prod_{\substack{1\le k\le n\\ k\ne j}}(x_j-x_k).$ For an integer $r\ge 0$, define...

taocpmathematicsalgorithmsvolume-1math-hard
TAOCP 1.2.3 Exercise 28

For $j \ge 2$, 1 - \frac{1}{j^2} = \frac{j^2 - 1}{j^2} = \frac{(j-1)(j+1)}{j^2} = \frac{j-1}{j} \cdot \frac{j+1}{j}.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.3 Exercise 30

Let $S=\sum_{j=1}^n a_j x_j,\qquad T=\sum_{j=1}^n b_j y_j.$ Then $ST=\left(\sum_{j=1}^n a_j x_j\right)\left(\sum_{k=1}^n b_k y_k\right)=\sum_{j=1}^n\sum_{k=1}^n a_j b_k x_j y_k. \eqno(1)$ Similarly, $...

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.3 Exercise 29

The iterated sum \sum_{i=0}^n \sum_{j=0}^i \sum_{k=0}^j a_i a_j a_k ranges over all integer triples satisfying

taocpmathematicsalgorithmsvolume-1math-hard
TAOCP 1.2.3 Exercise 25

The first equality \left(\sum_{i=1}^n a_i\right)\left(\sum_{j=1}^n \frac{1}{a_j}\right) = \sum_{1 \le i \le n} \sum_{1 \le j \le n} \frac{a_i}{a_j} follows directly from the distributive law (4), appl...

taocpmathematicsalgorithmsvolume-1simple
TAOCP 1.2.3 Exercise 27

Let $P_n = \prod_{j=1}^n (1 - a_j)$ and $S_n = \sum_{j=1}^n a_j$, where $0 < a_j < 1$ for each $j$.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.3 Exercise 24

Let $J$ be the finite set of all integers $j$ for which $R(j)$ is true, and let $|J| = n$.

taocpmathematicsalgorithmsvolume-1medium
TAOCP 1.2.3 Exercise 26

Let P=\prod_{i=0}^n \prod_{j=0}^i a_i a_j.

taocpmathematicsalgorithmsvolume-1medium
TAOCP 1.2.3 Exercise 22

The product notation is defined in Eq.

taocpmathematicsalgorithmsvolume-1medium
TAOCP 1.2.3 Exercise 23

When no integer satisfies $R(j)$, the expression $\sum_{R(j)} a_j$ must behave as an additive identity so that identities such as Eq.

taocpmathematicsalgorithmsvolume-1simple
TAOCP 1.2.3 Exercise 21

From (17), each restricted sum may be written as a full sum using Iverson’s convention: \sum_{R(j)} a_j = \sum_j a_j [R(j)], \qquad \sum_{S(j)} a_j = \sum_j a_j [S(j)].

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.3 Exercise 18

Let $R(i)$ be the relation “$i$ is a positive integer such that $n$ is a multiple of $i$,” equivalently $i \mid n$, and let $S(i,j)$ be the relation $1 \le j < i$.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.3 Exercise 19

$\sum_{j=m}^n (a_j - a_{j-1}) = \sum_{j=m}^n a_j - \sum_{j=m}^n a_{j-1}.$ The first term is unchanged.

taocpmathematicsalgorithmsvolume-1medium
TAOCP 1.2.3 Exercise 20

Let $k \ge 1$.

taocpmathematicsalgorithmsvolume-1medium
TAOCP 1.2.3 Exercise 17

Each term in $\sum_{j \in S} 1$ contributes the value $1$ once for every integer $j$ contained in $S$.

taocpmathematicsalgorithmsvolume-1math-immediate
TAOCP 1.2.3 Exercise 15

Let S_n = \sum_{k=1}^{n} k 2^k.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.3 Exercise 16

Let S=\sum_{j=0}^n jx^j.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.3 Exercise 14

Let $S=\sum_{j=m}^n \sum_{k=r}^s jk.$ For fixed $j$, the factor $j$ does not depend on $k$, hence $\sum_{k=r}^s jk = j \sum_{k=r}^s k.$ Substituting into $S$ gives $S=\sum_{j=m}^n \left(j \sum_{k=r}^s...

taocpmathematicsalgorithmsvolume-1simple
TAOCP 1.2.3 Exercise 13

From equation (15) with $a=0$ and $b=1$, $\sum_{0 \le j \le N} j = \frac{1}{2}N(N+1).$ This gives $\sum_{j=0}^n j = \frac{1}{2}n(n+1), \qquad \sum_{j=0}^{m-1} j = \frac{1}{2}(m-1)m.$ Since $m \le n$,...

taocpmathematicsalgorithmsvolume-1simple
TAOCP 1.2.3 Exercise 12

Let S = 1 + \frac{1}{7} + \frac{1}{7^2} + \cdots + \left(\frac{1}{7}\right)^n.

taocpmathematicsalgorithmsvolume-1simple
TAOCP 1.2.3 Exercise 10

No.

taocpmathematicsalgorithmsvolume-1simple
TAOCP 1.2.3 Exercise 11

If $x = 1$, each term $a x^j$ in the sum $\sum_{0 \le j \le n} a x^j$ becomes $a$.

taocpmathematicsalgorithmsvolume-1simple
TAOCP 1.2.3 Exercise 9

We consider the standard derivation of Eq.

taocpmathematicsalgorithmsvolume-1simple
TAOCP 1.2.3 Exercise 5

Let A_n=\sum_{i=1}^n a_i,\qquad B_m=\sum_{j=1}^m b_j, and assume both series $\sum_i a_i$ and $\sum_j b_j$ converge, so

taocpmathematicsalgorithmsvolume-1hm-medium
TAOCP 1.2.3 Exercise 7

Define the transformation $p(j)=c-j$.

taocpmathematicsalgorithmsvolume-1hm-medium
TAOCP 1.2.3 Exercise 6

Let $R,S \subseteq \mathbb{Z}$, and let $(a_j)$ be an arbitrary real-valued sequence.

taocpmathematicsalgorithmsvolume-1hm-medium
TAOCP 1.2.3 Exercise 8

Let $R(i)$ and $S(j)$ both be the relation $i \ge 0$ and $j \ge 0$.

taocpmathematicsalgorithmsvolume-1hm-medium
TAOCP 1.2.3 Exercise 1

The expression $a_1 + a_2 + \cdots + a_0$ contains no indices $j$ satisfying $1 \le j \le 0$, so it is a sum over an empty set of indices and is defined to be $0$.

taocpmathematicsalgorithmsvolume-1simple
TAOCP 1.2.3 Exercise 3

For the first sum, the condition $0 \le n \le 5$ restricts $n$ to the six integers $0,1,2,3,4,5$.

taocpmathematicsalgorithmsvolume-1simple
TAOCP 1.2.3 Exercise 2

The notation $\sum_{1 \le j \le n} a_j$ means the sum of $a_j$ over all integers $j$ satisfying $1 \le j \le n$.

taocpmathematicsalgorithmsvolume-1simple
TAOCP 1.2.3 Exercise 4

For $n = 3$, the left-hand side of Eq.

taocpmathematicsalgorithmsvolume-1simple
TAOCP 1.2.2 Exercise 29

For $b>1$, $b \log_b x = b \frac{\ln x}{\ln b} = (\ln x)\frac{b}{\ln b}.$ Since $x>1$, the factor $\ln x$ is positive and independent of $b$, so minimizing $b \log_b x$ is equivalent to minimizing $g(...

taocpmathematicsalgorithmsvolume-1hm-medium
TAOCP 1.2.2 Exercise 30

Let $t = \ln x$.

taocpmathematicsalgorithmsvolume-1simple
TAOCP 1.2.2 Exercise 28

The goal is to compute $b^x$ for $0 \le x < 1$ using only shifting, addition, and subtraction, and to analyze accuracy.

taocpmathematicsalgorithmsvolume-1math-hard
TAOCP 1.2.2 Exercise 27

The reviewer’s objections identify a real structural gap: the original proof implicitly assumed identical normalization behavior and uncontrolled error collapse.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.2 Exercise 25

The key error in the previous solution is the assumption that a right shift implements exact division by a power of two.

taocpmathematicsalgorithmsvolume-1medium
TAOCP 1.2.2 Exercise 24

Let $x > 0$.

taocpmathematicsalgorithmsvolume-1simple
TAOCP 1.2.2 Exercise 26

We restart from a consistent floating-point model and propagate the error through the iterative state update.

taocpmathematicsalgorithmsvolume-1math-hard
TAOCP 1.2.2 Exercise 23

Let $\ln x$ be interpreted as the area described in Fig.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.2 Exercise 22

For $x>0$, the binary, natural, and common logarithms are related by change of base: $\lg x = \frac{\ln x}{\ln 2}, \qquad \log_{10} x = \frac{\ln x}{\ln 10}.$ Hence $\ln x + \log_{10} x = \ln x \left(...

taocpmathematicsalgorithmsvolume-1medium
TAOCP 1.2.2 Exercise 21

Assume $b>0$, $b\ne 1$, and $x>1$ so that all logarithms and iterated logarithms are defined.

taocpmathematicsalgorithmsvolume-1simple
TAOCP 1.2.2 Exercise 18

Using the change of base formula (14) with base $2$, \log_8 x = \frac{\log_2 x}{\log_2 8}.

taocpmathematicsalgorithmsvolume-1simple
TAOCP 1.2.2 Exercise 19

A 14-digit decimal integer $n$ satisfies $10^{13} \le n \le 10^{14} - 1.$ A computer word with 47 bits for magnitude and one sign bit can represent integers in the range $- (2^{47} - 1) \le n \le 2^{4...

taocpmathematicsalgorithmsvolume-1medium
TAOCP 1.2.2 Exercise 17

$\lg 32 = \log_2 32 = 5$, because $2^5 = 32$.

taocpmathematicsalgorithmsvolume-1simple
TAOCP 1.2.2 Exercise 20

From equation (14), taking base $b=2$ and $c=10$, one obtains $\log_{10} 2 = \frac{\log_2 2}{\log_2 10}.$ Since $\log_2 2 = 1$ by equation (9), this simplifies to $\log_{10} 2 = \frac{1}{\log_2 10}.$...

taocpmathematicsalgorithmsvolume-1simple
TAOCP 1.2.2 Exercise 15

For $x,y>0$, write $\frac{x}{y} = x \cdot \frac{1}{y}.$ Using Eq.

taocpmathematicsalgorithmsvolume-1simple
TAOCP 1.2.2 Exercise 14

Let $b > 0$, $b \ne 1$, $c > 0$, and let $y$ be a real number.

taocpmathematicsalgorithmsvolume-1simple
TAOCP 1.2.2 Exercise 13

Let $x>0$ and let $n$ be a positive integer.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.2 Exercise 16

From equation (14), with $b = e$ and $c = 10$, one obtains $\log_{10} x = \frac{\log_e x}{\log_e 10}.$ By definition (15), $\log_e x = \ln x$ and $\log_e 10 = \ln 10$, hence $\log_{10} x = \frac{\ln x...

taocpmathematicsalgorithmsvolume-1
TAOCP 1.2.2 Exercise 11

Let $y = 10^x$.

taocpmathematicsalgorithmsvolume-1simple
TAOCP 1.2.2 Exercise 8

Let $m$ be a positive integer and let $u>0$.

taocpmathematicsalgorithmsvolume-1medium
TAOCP 1.2.2 Exercise 12

Since $10^x$ is strictly increasing for real $x$ when $10>1$, the inequalities in (8) imply $10^{0.30102999} < 2 < 10^{0.30103000}.$ Applying the monotonicity of $10^x$ and the definition of logarithm...

taocpmathematicsalgorithmsvolume-1simple
TAOCP 1.2.2 Exercise 9

Let $b>0$, and let $x=\frac{p}{q}$ and $y=\frac{r}{s}$, where $p,r\in\mathbb{Z}$ and $q,s$ are positive integers.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.2 Exercise 10

Assume that $\log_{10} 2$ is rational.

taocpmathematicsalgorithmsvolume-1medium
TAOCP 1.2.2 Exercise 6

The issue is that decimal expansions are not unique.

taocpmathematicsalgorithmsvolume-1simple
TAOCP 1.2.2 Exercise 4

We compute (0.

taocpmathematicsalgorithmsvolume-1simple
TAOCP 1.2.2 Exercise 5

A real number $x$ can be defined by a binary expansion $x = n + 0.b_1 b_2 b_3 \ldots,$ where $n$ is an integer and each $b_i \in {0,1}$, with the restriction that the sequence does not end in infinite...

taocpmathematicsalgorithmsvolume-1simple
TAOCP 1.2.2 Exercise 7

Let the exponentiation of an integer exponent be defined as in Eq.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.2 Exercise 1

Let $r$ be a positive rational number.

taocpmathematicsalgorithmsvolume-1
TAOCP 1.2.11.3 Exercise 20

The flaw in the previous solution is not the asymptotic analysis itself, but the unjustified introduction of the factor $(n/2)^{1-k/2}$.

taocpmathematicsalgorithmsvolume-1hm-hard
TAOCP 1.2.2 Exercise 2

The expression $1 + 0.239999999\ldots$ equals the real number whose fractional part is $0.239999999\ldots$, hence it represents $1.239999999\ldots$.

taocpmathematicsalgorithmsvolume-1
TAOCP 1.2.2 Exercise 3

Let $b^n$ be defined for integer $n$ by the rules in (4).

taocpmathematicsalgorithmsvolume-1simple
TAOCP 1.2.11.3 Exercise 17

For fixed integer $n>0$, consider the series S(n) = 1 + \frac{n}{n+1} + \frac{n}{n+1}\frac{n+1}{n+2} + \cdots = \sum_{k \ge 0} a_k,

taocpmathematicsalgorithmsvolume-1hm-hard
TAOCP 1.2.11.3 Exercise 18

The function $Q(n)$ is defined in this section so that its normalization removes the factor $n^n$ from sums of the form \sum_{k=0}^n \binom{n}{k} k^k (n-k)^{n-k}.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.11.3 Exercise 16

The previous argument fails because it never uses a valid definition of $Q(k)$ and therefore cannot justify any of the inversion steps.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.11.3 Exercise 19

Write C_n=\int_0^r e^{-nx}f(x)\,dx+\int_r^\infty e^{-nx}f(x)\,dx = A_n+B_n.

taocpmathematicsalgorithmsvolume-1hm-hard
TAOCP 1.2.11.3 Exercise 8

Start from the identity \left(1+\frac{u}{x}\right)^x = \exp\!

taocpmathematicsalgorithmsvolume-1hm-hard
TAOCP 1.2.11.3 Exercise 15

Consider I=\int_0^\infty \left(1+\frac{z}{n}\right)^n e^{-z}\,dz.

taocpmathematicsalgorithmsvolume-1hm-medium
TAOCP 1.2.11.3 Exercise 7

We restart from the integrand and determine all contributions that survive after integration down to order $O(x^{-2})$.

taocpmathematicsalgorithmsvolume-1hm-hard
TAOCP 1.2.11.3 Exercise 3

Start from Eq.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.11.3 Exercise 5

The errors in the previous solution stem from treating the Euler–Maclaurin remainder and the size of $f^{(3)}$ in a purely global way, and from introducing an unsupported “cancellation” step.

taocpmathematicsalgorithmsvolume-1hm-medium
TAOCP 1.2.11.3 Exercise 4

From the definition, v = u - \ln(1+u).

taocpmathematicsalgorithmsvolume-1hm-simple
TAOCP 1.2.11.3 Exercise 6

Start from the exact factorization \frac{(n+\alpha)^n}{n^{n+\beta}} = n^{-\beta}\left(1+\frac{\alpha}{n}\right)^n.

taocpmathematicsalgorithmsvolume-1hm-medium
TAOCP 1.2.11.2 Exercise 12

The previous solution fails because it treats a non-power-series manipulation as if it were coefficient algebra.

taocpmathematicsalgorithmsvolume-1hm-medium
TAOCP 1.2.11.2 Exercise 13

Assume $g(n)=\Omega(f(n))$.

taocpmathematicsalgorithmsvolume-1math-simple
TAOCP 1.2.11.3 Exercise 1

Let S_n(x)=\sum_{k=0}^{n}\frac{x^k}{k!

taocpmathematicsalgorithmsvolume-1hm-medium
TAOCP 1.2.11.3 Exercise 2

Let \gamma(a,x)=\int_0^x e^{-t}t^{a-1}\,dt,\qquad a>0,\ x\ge 0.

taocpmathematicsalgorithmsvolume-1hm-medium
TAOCP 1.2.11.2 Exercise 11

From the definition of the exponential function, e^x = \sum_{k\ge 0}\frac{x^k}{k!

taocpmathematicsalgorithmsvolume-1math-simple
TAOCP 1.2.11.2 Exercise 8

Let m = an^2 + bn.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.11.2 Exercise 9

Let \binom{2n}{n}=\frac{(2n)!

taocpmathematicsalgorithmsvolume-1math-medium
CF 105348C - String Traversal Paradigm 1

We are given a string s of length n, and we should think of every occurrence of a character as a position on a line. Moving between two positions has a cost that depends on whether the characters are the same.

codeforcescompetitive-programming
TAOCP 1.2.11.2 Exercise 10

Let $u(z)=O(z^m)$ as $z\to 0$.

taocpmathematicsalgorithmsvolume-1hm-medium
TAOCP 1.2.11.2 Exercise 4

Let $f(x)=x^m$.

taocpmathematicsalgorithmsvolume-1hm-medium
TAOCP 1.2.11.2 Exercise 6

We restart the argument using a representation of $\Gamma$ that avoids any delicate extraction from the digamma kernel.

taocpmathematicsalgorithmsvolume-1hm-hard
TAOCP 1.2.11.2 Exercise 7

Let P_n = 1^1 2^2 3^3 \cdots n^n.

taocpmathematicsalgorithmsvolume-1hm-hard
TAOCP 1.2.11.2 Exercise 5

Assume n!

taocpmathematicsalgorithmsvolume-1hm-hard
TAOCP 1.2.11.2 Exercise 1

Equation (7) in Section 1.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.11.2 Exercise 2

Equation (10) is obtained in Euler’s summation formula by repeated application of finite-difference identities that depend on a specific sequence of coefficients introduced in Eq.

taocpmathematicsalgorithmsvolume-1hm-medium
TAOCP 1.2.11.2 Exercise 3

Let $m=2k>0$ and assume $f^{(m)}(x)$ has constant sign on $1\le x\le n$.

taocpmathematicsalgorithmsvolume-1hm-medium
TAOCP 1.2.10 Exercise 19

Let $a_1a_2\ldots a_n$ be a permutation of ${1,2,\ldots,n}$ and let $b_1b_2\ldots b_n$ be its inverse, so that a_k = l \iff b_l = k.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.10 Exercise 21

The error in the previous solution is not in the Chernoff optimization step or the reduction to a KL divergence, but in the justification of the quadratic lower bound.

taocpmathematicsalgorithmsvolume-1hm-medium
TAOCP 1.2.10 Exercise 20

Let $d_k = a_k - b_k$, where $b_1 \le b_2 \le \cdots \le b_n$.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.10 Exercise 22

Let $G(z)=\prod_{k=1}^n (q_k+p_k z)$ be the probability generating function of $X$.

taocpmathematicsalgorithmsvolume-1hm-medium
TAOCP 1.2.10 Exercise 16

Let $g_i(z)=\sum_k p^{(i)}_k z^k$ be the generating function of distribution $g_i$, so $p^{(i)}_k$ is the probability that the value equals $k$.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.10 Exercise 18

Let the multiset consist of $k_i$ copies of value $i$, $1\le i\le n$, with \sum_{i=1}^n k_i = n.

taocpmathematicsalgorithmsvolume-1math-hard
TAOCP 1.2.10 Exercise 15

The probability that the quantity has value $k$ is $e^{-\mu}\frac{\mu^k}{k!}$.

taocpmathematicsalgorithmsvolume-1hm-medium
TAOCP 1.2.10 Exercise 17

Let f(z)=\sum_{k\ge 0} a_k z^k,\qquad g(z)=\sum_{n\ge 0} b_n z^n be probability generating functions.

taocpmathematicsalgorithmsvolume-1math-hard
TAOCP 1.2.10 Exercise 11

Let $G(z)=\sum_k p_k z^k$ be the probability generating function of a distribution for a random variable $A$.

taocpmathematicsalgorithmsvolume-1math-simple