brain

tamnd's digital brain — notes, problems, research

43815 notes

TAOCP 1.2.5 Exercise 25

Factorial powers, defined by $x^{\overline{n}} = x(x+1)\cdots(x+n-1), \qquad x^{\underline{n}} = x(x-1)\cdots(x-n+1),$ do not satisfy a simple law analogous to ordinary exponentiation, $x^{m+n} = x^m...

taocpmathematicsalgorithmsvolume-1
TAOCP 1.2.5 Exercise 23

For integers $m$ and $n$, we have (a) Let $m = qn + r$ with $0 \le r < n$.

taocpmathematicsalgorithmsvolume-1
TAOCP 1.2.5 Exercise 21

The natural hypothesis is \frac{(n+x)!

taocpmathematicsalgorithmsvolume-1
TAOCP 1.2.5 Exercise 18

By exercise 17, with $k=1$,By equation (13), \left(\tfrac12\right)!

taocpmathematicsalgorithmsvolume-1
TAOCP 1.2.5 Exercise 16

Let c_k=1-\frac1{1!

taocpmathematicsalgorithmsvolume-1
TAOCP 1.2.5 Exercise 17

Let P_N=\prod_{n=1}^{N}\frac{(n+\alpha_1)\cdots(n+\alpha_k)} {(n+\beta_1)\cdots(n+\beta_k)}.

taocpmathematicsalgorithmsvolume-1
TAOCP 1.2.5 Exercise 19

By Eq.

taocpmathematicsalgorithmsvolume-1
TAOCP 1.2.5 Exercise 15

Let $A=(a_{ij})$ be the given matrix, where $a_{ij}=i,j$.

taocpmathematicsalgorithmsvolume-1
TAOCP 1.2.5 Exercise 13

For each $a\in{1,2,\ldots,p-1}$ there is a unique inverse $a^{-1}$ modulo $p$, since $p$ is prime.

taocpmathematicsalgorithmsvolume-1
TAOCP 1.2.5 Exercise 9

By definition of the Gamma function, we have $\Gamma(x) = (x-1)!$ for positive real $x$, and $(\tfrac12)! = \Gamma(\tfrac12+1) = \Gamma(\tfrac32)$.

taocpmathematicsalgorithmsvolume-1
TAOCP 1.2.5 Exercise 7

By Eq.

taocpmathematicsalgorithmsvolume-1
TAOCP 1.2.5 Exercise 3

Using Method 1, insert $5$ into every possible position of the permutation $3124$: $53124,\qquad 35124,\qquad 31524,\qquad 31254,\qquad 31245.$ Using Method 2, let $k=1,2,3,4,5$.

taocpmathematicsalgorithmsvolume-1
TAOCP 1.2.5 Exercise 5

Using the refined approximation with $n=8$, 8!

taocpmathematicsalgorithmsvolume-1
TAOCP 1.2.5 Exercise 8

Let $n$ be a nonnegative integer.

taocpmathematicsalgorithmsvolume-1
TAOCP 1.2.4 Exercise 45

Let $m,n>0$ and let $f$ be defined on $\{0,1,\dots,m-1\}$.

taocpmathematicsalgorithmsvolume-1math-hard
TAOCP 1.2.5 Exercise 1

A 52-card deck consists of 52 distinct objects.

taocpmathematicsalgorithmsvolume-1
TAOCP 1.2.4 Exercise 46

Let $m,n$ be positive integers and let $\alpha>0$ be real.

taocpmathematicsalgorithmsvolume-1math-hard
TAOCP 1.2.4 Exercise 43

Let $m=\lfloor \sqrt{n}\rfloor$.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.4 Exercise 44

The positive case is correct, but the negative case fails because the telescoping argument silently assumes that $\left\lfloor \frac{n}{b^k} \right\rfloor \to 0$ as $k \to \infty$, which is false for...

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.4 Exercise 42

Let S = n a_n - \sum_{k=1}^{n-1} k(a_{k+1}-a_k).

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.4 Exercise 41

Let $T_k = \frac{k(k+1)}{2}$ for $k \ge 1$.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.4 Exercise 40

The previous solution failed at a more basic level: it solved a different equation and then attempted an unjustified structural argument.

taocpmathematicsalgorithmsvolume-1hm-research
TAOCP 1.2.4 Exercise 37

Let $d=\gcd(m,n)$ and write m=d m_1,\qquad n=d n_1,\qquad \gcd(m_1,n_1)=1.

taocpmathematicsalgorithmsvolume-1math-hard
TAOCP 1.2.4 Exercise 36

Let $n \in \mathbb{Z}$, $n \ge 1$.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.4 Exercise 39

A function $f$ is _replicative_ if for every real $x$ and every positive integer $n$, \sum_{k=0}^{n-1} f\!

taocpmathematicsalgorithmsvolume-1hm-hard
TAOCP 1.2.4 Exercise 38

Let $x,y \in \mathbb{R}$ with $y>0$.

taocpmathematicsalgorithmsvolume-1math-hard
TAOCP 1.2.4 Exercise 35

Write $x = \lfloor x \rfloor + r$ with $0 \le r < 1$.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.4 Exercise 34

We determine all real bases $b>1$ for which \lfloor \log_b x \rfloor = \lfloor \log_b \lfloor x \rfloor \rfloor \quad \text{for all } x \ge 1.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.4 Exercise 33

Let $n,m \in \mathbb{Z}$.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.4 Exercise 29

Let $f$ be a function on positive integers.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.4 Exercise 32

All sums are finite since the set of positive divisors of $n$ is finite.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.4 Exercise 30

Let $\varphi(n)$ denote the number of integers $a$ with $1 \le a \le n$ such that $a \perp n$.

taocpmathematicsalgorithmsvolume-1math-hard
TAOCP 1.2.4 Exercise 31

Let $r \perp s$.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.4 Exercise 27

We restart from the definition.

taocpmathematicsalgorithmsvolume-1math-simple
TAOCP 1.2.4 Exercise 26

Let $p$ be an odd prime and let $a$ be an integer.

taocpmathematicsalgorithmsvolume-1math-simple
TAOCP 1.2.4 Exercise 25

Let $p$ be prime.

taocpmathematicsalgorithmsvolume-1math-simple
TAOCP 1.2.4 Exercise 28

Let $m$ be a positive integer and let $a \perp m$.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.4 Exercise 24

Let congruence for real numbers be defined by x \equiv y \pmod m \quad \Longleftrightarrow \quad x-y \in m\mathbb{Z}, \quad m \neq 0, where $m\mathbb{Z}=\{mk : k\in\mathbb{Z}\}$.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.4 Exercise 23

Take $r=s=2$, so $rs=4$, and $a=2$, $b=0$.

taocpmathematicsalgorithmsvolume-1math-simple
TAOCP 1.2.4 Exercise 22

Let $m=4$, $a=2$, $b=2$, $x=0$, $y=2$.

taocpmathematicsalgorithmsvolume-1math-simple
TAOCP 1.2.4 Exercise 18

Let $r \perp s$ and assume $a \equiv b \pmod r$ and $a \equiv b \pmod s$.

taocpmathematicsalgorithmsvolume-1math-simple
TAOCP 1.2.4 Exercise 20

Since $a \perp m$, the law of inverses yields an integer $a'$ such that aa' \equiv 1 \pmod m.

taocpmathematicsalgorithmsvolume-1math-simple
TAOCP 1.2.4 Exercise 21

Let $n>1$.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.4 Exercise 19

Since $n \perp m$, the greatest common divisor of $n$ and $m$ is $1$.

taocpmathematicsalgorithmsvolume-1math-simple
TAOCP 1.2.4 Exercise 17

Let $m$ be a fixed integer.

taocpmathematicsalgorithmsvolume-1math-simple
TAOCP 1.2.4 Exercise 16

Let $k = (x - z)/y$, where $k \in \mathbb{Z}$.

taocpmathematicsalgorithmsvolume-1math-simple
TAOCP 1.2.4 Exercise 15

If $y \ne 0$ and $z \ne 0$, then by definition (1), x \bmod y = x - y\left\lfloor \frac{x}{y} \right\rfloor.

taocpmathematicsalgorithmsvolume-1simple
TAOCP 1.2.4 Exercise 14

From $x \bmod 5 = 3$, there exists an integer $k$ such that $x = 3 + 5k.$ Impose the condition $x \bmod 3 = 2$ by reducing the expression modulo $3$: $3 + 5k \equiv 2 \pmod 3.$ Since $3 \equiv 0 \pmod...

taocpmathematicsalgorithmsvolume-1simple
TAOCP 1.2.4 Exercise 11

By definition (5), $x \equiv y \pmod z$ means $x \bmod z = y \bmod z$.

taocpmathematicsalgorithmsvolume-1
TAOCP 1.2.4 Exercise 12

For any integer $x$, every common divisor of $x$ and $1$ must divide $1$, hence the only positive common divisor is $1$.

taocpmathematicsalgorithmsvolume-1
TAOCP 1.2.4 Exercise 13

By convention, $\gcd(0,n)=|n|$.

taocpmathematicsalgorithmsvolume-1math-immediate
TAOCP 1.2.4 Exercise 10

Using the definition $x \bmod y = x - y\lfloor x/y \rfloor$ for $y \ne 0$: For $1.1 \bmod 1$, compute $\lfloor 1.1/1 \rfloor = \lfloor 1.1 \rfloor = 1$.

taocpmathematicsalgorithmsvolume-1simple
TAOCP 1.2.4 Exercise 8

Using $x \bmod y = x - y\lfloor x/y \rfloor$ for $y \ne 0$ and $x \bmod 0 = x$: For $100 \bmod 3$, one has $\lfloor 100/3 \rfloor = 33$, hence $100 \bmod 3 = 100 - 3 \cdot 33 = 1$.

taocpmathematicsalgorithmsvolume-1
TAOCP 1.2.4 Exercise 9

For $y<0$, the definition is $x \bmod y = x - y\lfloor x/y \rfloor$, and the quotient is determined by the floor of the real number $x/y$.

taocpmathematicsalgorithmsvolume-1simple
TAOCP 1.2.4 Exercise 5

Let $x$ be a positive real number.

taocpmathematicsalgorithmsvolume-1medium
TAOCP 1.2.4 Exercise 7

Write $x = \lfloor x \rfloor + a$, $y = \lfloor y \rfloor + b$, where $a = \{x\}$, $b = \{y\}$, so $0 \le a,b < 1$.

taocpmathematicsalgorithmsvolume-1math-simple
TAOCP 1.2.4 Exercise 6

Let $x>0$ and set $n=\lfloor x\rfloor$.

taocpmathematicsalgorithmsvolume-1medium
TAOCP 1.2.4 Exercise 4

Let $n = \lfloor -x \rfloor$.

taocpmathematicsalgorithmsvolume-1math-simple
TAOCP 1.2.4 Exercise 2

Let $n = \lfloor x \rfloor$.

taocpmathematicsalgorithmsvolume-1simple
TAOCP 1.2.4 Exercise 3

Let $n$ be an integer.

taocpmathematicsalgorithmsvolume-1math-simple
TAOCP 1.2.3 Exercise 45

Let H=(h_{ij})_{1\le i,j\le n}, \qquad h_{ij}=\frac1{i+j-1}.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.3 Exercise 46

We restart from the correct expansion and repair only the faulty combinatorial step by eliminating the incorrect bijection claim and replacing it with a valid classification of _injective_ maps.

taocpmathematicsalgorithmsvolume-1math-hard
TAOCP 1.2.4 Exercise 1

$\lfloor 1.1 \rfloor = 1$ since $1 \le 1.1 < 2$.

taocpmathematicsalgorithmsvolume-1
TAOCP 1.2.3 Exercise 44

Let A=(a_{ij}), \qquad a_{ij}=\frac1{x_i+y_j}, \qquad 1\le i,j\le n, be Cauchy's matrix, and let

taocpmathematicsalgorithmsvolume-1math-hard
TAOCP 1.2.3 Exercise 42

By Exercise 39, the inverse of the combinatorial matrix has entries b_{ij}=\frac{-y+\delta_{ij}(x+ny)}{x(x+ny)}.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.3 Exercise 43

Let $V$ be the Vandermonde matrix with entries $V_{ij} = x_i^{j-1}$ for $1 \le i, j \le n$, and let $B = V^{-1}$ with entries $b_{ij}$.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.3 Exercise 38

Let D_n=\det\!

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.3 Exercise 40

Let $V$ be the $n\times n$ Vandermonde matrix $V_{ij}=x_i^{\,j-1}$, with $x_1,\dots,x_n$ distinct.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.3 Exercise 39

Let $A = (a_{ij})_{1 \le i,j \le n}$ be the combinatorial matrix with entries $a_{ij} = x + y\,[i \ne j],$ equivalently $a_{ij} = y + x\,\delta_{ij}.$ Let $B = (b_{ij})_{1 \le i,j \le n}$ be defined b...

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.3 Exercise 41

Let $A = (a_{ik})$ be the Cauchy matrix defined by $a_{ik} = \frac{1}{x_i + y_k}, \qquad 1 \le i,k \le n,$ where all quantities $x_i + y_k$, $x_j - x_k$, and $y_i - y_k$ that appear below are nonzero.

taocpmathematicsalgorithmsvolume-1math-hard
TAOCP 1.2.3 Exercise 36

Let $A = (a_{ij})_{1 \le i,j \le n}$ be the combinatorial matrix defined by $a_{ij} = y + \delta_{ij} x,$ so that $a_{ii} = x+y$ and $a_{ij} = y$ when $i \ne j$.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.3 Exercise 37

Let $A = (a_{ij})$ be the $n \times n$ matrix defined by $a_{ij} = x_j^i$.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 1.2.3 Exercise 35

Let M=\sup_{R(i)} a_i,\qquad N=\sup_{S(j)} b_j.

taocpmathematicsalgorithmsvolume-1hm-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 34

Let P(t)=\prod_{r=1}^n (t-r).

taocpmathematicsalgorithmsvolume-1math-medium
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 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 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 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 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 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 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 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 22

The product notation is defined in Eq.

taocpmathematicsalgorithmsvolume-1medium
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 20

Let $k \ge 1$.

taocpmathematicsalgorithmsvolume-1medium
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 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 15

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

taocpmathematicsalgorithmsvolume-1math-medium
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 16

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

taocpmathematicsalgorithmsvolume-1math-medium
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 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 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 8

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

taocpmathematicsalgorithmsvolume-1hm-medium