TAOCP 1.2.3: Sums and Products
Section 1.2.3 exercises: 46/46 solved.
Section 1.2.3. Sums and Products
Exercises from TAOCP Volume 1 Section 1.2.3: 46/46 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | ▶ [10] | simple | verified | 34s |
| 2 | [01] | simple | verified | 1m01s |
| 3 | ▶ [13] | simple | verified | 44s |
| 4 | [10] | simple | verified | 45s |
| 5 | ▶ [HM20] | hm-medium | verified | 2m22s |
| 6 | [HM20] | hm-medium | verified | 2m06s |
| 7 | [HM23] | hm-medium | verified | 37s |
| 8 | [HM25] | hm-medium | verified | 35s |
| 9 | ▶ [05] | simple | verified | 1m04s |
| 10 | [05] | simple | verified | 3m06s |
| 11 | [03] | simple | verified | 34s |
| 12 | [10] | simple | verified | 36s |
| 13 | [10] | simple | verified | 37s |
| 14 | [11] | simple | verified | 32s |
| 15 | ▶ [M22] | math-medium | verified | 1m15s |
| 16 | [M22] | math-medium | verified | 31s |
| 17 | ▶ [M00] | math-immediate | verified | 34s |
| 18 | [M20] | math-medium | verified | 34s |
| 19 | [20] | medium | verified | 2m02s |
| 20 | ▶ [25] | medium | verified | 1m31s |
| 21 | ▶ [M25] | math-medium | verified | 34s |
| 22 | ▶ [20] | medium | verified | 1m44s |
| 23 | [10] | simple | verified | 39s |
| 24 | [20] | medium | verified | 33s |
| 25 | ▶ [15] | simple | verified | 59s |
| 26 | [25] | medium | verified | 35s |
| 27 | [M20] | math-medium | verified | 41s |
| 28 | [M22] | math-medium | verified | 35s |
| 29 | ▶ [M30] | math-hard | verified | 38s |
| 30 | ▶ [M23] | math-medium | verified | 44s |
| 31 | [M20] | math-medium | verified | 1m06s |
| 32 | [M20] | math-medium | verified | 29s |
| 33 | ▶ [M30] | math-hard | verified | 41s |
| 34 | [M25] | math-medium | solved | 3m14s |
| 35 | [HM20] | hm-medium | verified | 45s |
| 36 | [M23] | math-medium | verified | 45s |
| 37 | ▶ [M24] | math-medium | verified | 33s |
| 38 | ▶ [M25] | math-medium | verified | 5m11s |
| 39 | [M23] | math-medium | verified | 2m20s |
| 40 | [M24] | math-medium | verified | 5m58s |
| 41 | [M26] | math-hard | verified | 3m24s |
| 42 | [M18] | math-medium | verified | 35s |
| 43 | [M24] | math-medium | verified | 39s |
| 44 | ▶ [M26] | math-hard | verified | 3m29s |
| 45 | ▶ [M25] | math-medium | solved | 4m35s |
| 46 | ▶ [M30] | math-hard | solved | 11m02s |
TAOCP 1.2.3 Exercise 1
By definition, a sum of the form $a_1 + a_2 + \cdots + a_0$ is empty because the upper limit is less than the lower limit.
TAOCP 1.2.3 Exercise 2
By definition (2), $\sum_{1 \le j \le n} a_j$ denotes the sum of all terms $a_j$ for integer values of $j$ satisfying the condition $1 \le j \le n$.
TAOCP 1.2.3 Exercise 3
The first sum is $\sum_{0 \le n \le 5} \frac{1}{2n+1}.$ The integers satisfying $0 \le n \le 5$ are $n=0,1,2,3,4,5.$ Hence
TAOCP 1.2.3 Exercise 4
For $n = 3$, the left-hand side of Eq.
TAOCP 1.2.3 Exercise 5
Let \sum_{R(i)} a_i = A, \qquad \sum_{S(j)} b_j = B
TAOCP 1.2.3 Exercise 6
Let A=\sum_{R(j)} a_j,\qquad B=\sum_{S(j)} a_j,\qquad C=\sum_{R(j)\text{ or }S(j)} a_j,\qquad D=\sum_{R(j)\text{ and }S(j)} a_j .
TAOCP 1.2.3 Exercise 7
Let $S=\sum_{R(j)} a_j.$ Define the change of variable $i=c-j.$ Since $c$ is an integer, the mapping $j \mapsto c-j$
TAOCP 1.2.3 Exercise 8
Equation (7) asserts that \sum_{R(i)} \sum_{S(j)} a_{ij} = \sum_{S(j)} \sum_{R(i)} a_{ij}.
TAOCP 1.2.3 Exercise 9
Yes.
TAOCP 1.2.3 Exercise 10
Let S=\sum_{0\le j\le n} ax^j .
TAOCP 1.2.3 Exercise 11
If $x = 1$, the left-hand side of Eq.
TAOCP 1.2.3 Exercise 12
The given sum is a finite geometric progression with first term $a = 1$, common ratio $x = \frac{1}{7}$, and $n+1$ terms.
TAOCP 1.2.3 Exercise 13
We begin by expressing the sum in a form suitable for applying Eq.
TAOCP 1.2.3 Exercise 14
By the distributive law (4), \sum_{j=m}^n \sum_{k=r}^s jk = \left(\sum_{j=m}^n j\right)\left(\sum_{k=r}^s k\right).
TAOCP 1.2.3 Exercise 15
Let S_n=\sum_{j=1}^{n} j2^j.
TAOCP 1.2.3 Exercise 16
Let S=\sum_{j=0}^n jx^j.
TAOCP 1.2.3 Exercise 17
By definition, $\sum_{j \in S} 1$ is the sum of one copy of $1$ for each integer $j$ belonging to $S$.
TAOCP 1.2.3 Exercise 18
We are to transform $\sum_{R(i)} \sum_{S(i,j)} a_{ij}$ according to Eq.
TAOCP 1.2.3 Exercise 19
We compute the sum directly.
TAOCP 1.2.3 Exercise 20
The observed identities are 9\cdot 1+2=11,\qquad 9\cdot 12+3=111,\qquad 9\cdot 123+4=1111,\qquad 9\cdot 1234+5=11111.
TAOCP 1.2.3 Exercise 21
By Eq.
TAOCP 1.2.3 Exercise 22
The required product analogs are obtained by replacing sums with products and interpreting repeated factors with multiplicity.
TAOCP 1.2.3 Exercise 23
Defining $\sum_{R(j)} a_j = 0$ when no integers satisfy $R(j)$ preserves the additive identity.
TAOCP 1.2.3 Exercise 24
Let P(R)=\prod_{R(j)} a_j, \qquad S(R)=\sum_{R(j)} (\log_b a_j),
TAOCP 1.2.3 Exercise 25
We are asked to examine the derivation $\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} = \sum_{1 \le i \le n} \su...
TAOCP 1.2.3 Exercise 26
Let P=\prod_{i=0}^n \prod_{j=0}^i a_i a_j.
TAOCP 1.2.3 Exercise 27
We proceed by induction on $n$.
TAOCP 1.2.3 Exercise 28
Write 1-\frac1{j^2} = \frac{(j-1)(j+1)}{j^2} =
TAOCP 1.2.3 Exercise 29
Define S=\sum_{i=0}^n \sum_{j=0}^i \sum_{k=0}^j a_i a_j a_k.
TAOCP 1.2.3 Exercise 30
Let A=\sum_{j=1}^n a_jx_j,\qquad B=\sum_{j=1}^n b_jy_j, and
TAOCP 1.2.3 Exercise 31
Apply Binet's formula from Exercise 30 with the substitutions a_j=u_j,\qquad b_j=1,\qquad x_j=1,\qquad y_j=v_j.
TAOCP 1.2.3 Exercise 32
We proceed by induction on $n$.
TAOCP 1.2.3 Exercise 33
Let $x_1, x_2, \ldots, x_n$ be distinct numbers, and define, for $0 \le r \le n$, S_r := \sum_{j=1}^n \frac{x_j^r}{\prod_{\substack{1 \le k \le n \\ k \ne j}} (x_j - x_k)}.
TAOCP 1.2.3 Exercise 34
Let f(x)=\sum_{k=1}^n \frac{\displaystyle\prod_{\substack{1\le r\le n\\ r\ne m}}(x+k-r)} {\displaystyle\prod_{\substack{1\le r\le n\\ r\ne k}}(k-r)}.
TAOCP 1.2.3 Exercise 35
Let M = \sup_{R(j)} a_j .
TAOCP 1.2.3 Exercise 36
Let $A = (a_{ij})$ be the $n \times n$ combinatorial matrix with entries $a_{ij} = y + \delta_{ij} x = \begin{cases} x + y, & i = j, \\ y, & i \ne j. \end{cases}$ We want to show that $\det(A) = x^{n-...
TAOCP 1.2.3 Exercise 37
Let $V_n = (a_{ij})_{1 \le i,j \le n}$ denote the $n \times n$ Vandermonde matrix, where $a_{ij} = x_j^i$.
TAOCP 1.2.3 Exercise 38
Let D_n=\det\!
TAOCP 1.2.3 Exercise 39
Let $A = (a_{ij})_{1 \le i,j \le n}$ be the combinatorial matrix, where $a_{ij} = x\delta_{ij} + y.$ Thus $A = xI + yJ,$ where $I$ is the identity matrix and $J$ is the matrix whose entries are all eq...
TAOCP 1.2.3 Exercise 40
Let A=(a_{ij})_{1\le i,j\le n}, \qquad a_{ij}=x_i^{\,j-1},
TAOCP 1.2.3 Exercise 41
Let $A=(a_{ij})_{1\le i,j\le n}$ be Cauchy’s matrix, where $a_{ij}=\frac1{x_i+y_j}.$ Let $B=(b_{ij})$ be the matrix whose entries are b_{ij} = \frac{
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)}.
TAOCP 1.2.3 Exercise 43
Let $V = (v_{ij})$ be the $n \times n$ Vandermonde matrix with entries $v_{ij} = x_i^{j-1}$ for $1 \le i, j \le n$, and let $B = (b_{ij})$ denote its inverse.
TAOCP 1.2.3 Exercise 44
Let A=(a_{ij})_{1\le i,j\le n}, \qquad a_{ij}=\frac1{x_i+y_j},