README.org (20905B)
1 #+Title: The Art of Computer Programming
2 #+Subtitle: Notes
3 #+Author: Shimmy Xu
4 #+LaTeX_CLASS: article
5 #+LaTeX_HEADER: \usepackage{amsmath,amssymb,amsthm,placeins,esint,bm}
6 #+INCLUDE: "~/.emacs.d/static/math_macros.sty" src latex-macros
7 #+Options: toc:nil num:t
8 #+STARTUP: logdone
9 #+TODO: INACTIVE TODO | DONE
10
11 * TODO The Art of Computer Programming Volume 1: Fundamental Algorithms
12 ** TODO Chapter 1: Basic concepts
13 *** TODO 1.1 Algorithms
14 :LOGBOOK:
15 CLOCK: [2020-12-28 Mon 19:54]--[2020-12-28 Mon 20:26] => 0:32
16 :END:
17 *** TODO 1.2 Mathematical Preliminaries
18 :LOGBOOK:
19 CLOCK: [2021-01-03 Sun 16:03]--[2021-01-03 Sun 18:28] => 2:25
20 CLOCK: [2020-12-30 Tue 20:50]--[2020-12-30 Wed 21:20] => 0:30
21 CLOCK: [2020-12-29 Tue 20:11]--[2020-12-29 Wed 21:30] => 1:19
22 CLOCK: [2020-12-28 Mon 20:27]--[2020-12-28 Mon 21:29] => 1:02
23 :END:
24 **** 1.2.1
25 ***** DONE 1
26 CLOSED: [2021-01-10 Sun 06:35]
27 Change all occurrences of \(P(1)\) to \(P(0)\). In I1, set \(k \left 0\).
28 ***** DONE 2
29 CLOSED: [2021-01-10 Sun 06:35]
30 When \(n = 1\), the quantity \(b = a^(n-2)/(n-1)\) is not defined due to division by zero.
31 ***** INACTIVE 3
32 ***** TODO 4
33 ***** INACTIVE 5
34 ***** DONE 6
35 CLOSED: [2021-01-10 Sun 06:35]
36 \(a'm + b'n = c\) is trivial as it's \(am + bn = d\) after rename in E4.
37 Given Eqs. (6) and \(c = qd + r\), we also have:
38 \begin{align*}
39 r
40 &= c - qd\\
41 &= (a'm + b'n) - q(am + bn)\\
42 &= (a' - qa)m + (b' - qb)n.
43 \end{align*}
44 After E4, this equality becomes \(am + bn = d\).
45 **** 1.2.2
46 Never thought about the not ending in infinitely many 9s part.
47 **** 1.2.3
48 I knew Kronecker delta, but not Iverson's convention.
49 ***** 29
50 1.2.9
51
52 **** 1.2.4
53 The construction of \(x \mod y\) here is well defined when \(y < 0\).
54 ***** DONE 35
55 CLOSED: [2021-01-10 Sun 06:34]
56 Note that \(0 \leq x - \floor{x} < 1\), so we have \(x \mod n = \floor{x} \mod n + (x - \floor{x})\).
57 \begin{align*}
58 n \floor{(x + m) / n}
59 &= (x - m) - (x + m) \mod m\\
60 &= (x - m) - (\floor{x + m} \mod m + (x + m - \floor{x + m}))\\
61 &= (\floor{x} - m) - (\floor{x} + m) \mod m\\
62 &= n \floor((\floor{x} + m) / n),\\
63 \floor{(x + m) / n}
64 &= \floor((\floor{x} + m) / n).
65 \end{align*}
66
67 **** 1.2.5
68 Method II conditions on the last number being \(k\), effectively.
69 Ah Stirling's appproximation.
70
71 2nd equality in (20): just a sign trick.
72
73 ***** 18
74
75 ***** 20
76 **** 1.2.6
77 Note how the \(r\) in \({r \choose k} = \frac{r^{\underline{k}}}{k!}\) is real.
78
79 \(n + 1\) point equality proof for \(n\)-th order polynomials is a neat argument.
80
81 (9) is again, conditioning on last element.
82
83 Never seen E before, related proof for sum of squares is cool.
84
85 For binomial theorem, when \(r < 0\), where does the \(\abs{x/y} < 1\) restriction comes from?
86 As now the series is infinite, and for
87 \begin{align*}
88 \sum_{k}{r \choose k}x^{k}y^{r-k}
89 &= y^{r}\sum_{k}{r \choose k}(\frac{x}{y})^{k},
90 \end{align*}
91 that's a necessary condition for convergence.
92
93 Abel's (16) is interesting.
94
95 Proof for (17):
96 \begin{align*}
97 {r \choose k}
98 &= \frac{r(r - 1)\dots(r - k + 1)}{k!}\\
99 &= (-1)^{k}\frac{(-r)(1 - r)\dots(k - r - 1)}{k!}\\
100 &= (-1)^{k}\frac{(k - r - 1)\dots((k - r - 1) - k)((k - r - 1) - (k - 1))}{k!}\\
101 &= (-1)^{k}{k - r - 1 \choose k}.
102 \end{align*}
103
104 Proof for (35):
105 \begin{align*}
106 \sum_{k}{r \choose k}{s - kt \choose r}(-1)^{k}
107 &= \sum_{k}{r \choose k}\frac{(s - kt)(s - kt - 1)\dots(s - kt - r + 1)}{r!}(-1)^{k}\\
108 &= \sum_{k}{r \choose k}\frac{(kt - s)(kt - s + 1)\dots(kt - s + r - 1)}{r!}(-1)^{r - k}(-1)^{2k}\\
109 &= \frac{1}{r!}\sum_{k}{r \choose k}(-1)^{r - k}(tk - s)(tk - s + 1)\dots(tk - s + r - 1)\\
110 &= \frac{1}{r!}\sum_{k}{r \choose k}(-1)^{r - k}(b_{0} + b_{1}tk + \cdots + t^{r}k^{r}),
111 \end{align*}
112 for some \(b_{i}\). Applying (34) gives the answer \(t^{r}\).
113
114 Try to prove (37) and (38).
115
116 Check /Concrete Math/ 5.8 for Gosper-Zeilberger algorithm and 6.1 for Stirling numbers.
117
118 ***** TODO 25
119
120 ***** INACTIVE 36
121 ***** INACTIVE 40
122 ***** INACTIVE 41
123 ***** INACTIVE 42
124 ***** INACTIVE 43
125 ***** INACTIVE 44
126 ***** INACTIVE 45
127 ***** DONE 50
128 CLOSED: [2021-01-03 Sun 17:02]
129 When \(x + y = 0\), we have by applying (17) and that \(n - k > -1 - k\),
130 \begin{align*}
131 &\quad\sum_{k}{n \choose k}x(x - kz)^{k - 1}(y + kz)^{n - k}\\
132 &= \sum_{k}{n \choose k}x(x - kz)^{k - 1}(-x + kz)^{n - k}\\
133 &= \sum_{k}(-1)^{n - k}{n \choose k}x(x - kz)^{n - 1}\\
134 &= \sum_{k}(-1)^{n - k}{n \choose n - k}x(x - kz)^{n - 1}\\
135 &= \sum_{k}{-1 - k \choose n - k}x(x - kz)^{n - 1}\\
136 &= 0\\
137 &= (x + y)^{n}.
138 \end{align*}
139
140 ***** DONE 51
141 CLOSED: [2021-01-03 Sun 17:52]
142 Writing \(y = (x + y) - x\), we have by (20),
143 \begin{align*}
144 &\quad\sum_{k}{n \choose k}x(x - kz)^{k - 1}((x + y) - x + kz)^{n - k}\\
145 &= \sum_{k}{n \choose k}x(x - kz)^{k - 1}\sum_{l}(-1)^{n - k - l}{n - k \choose l}(x + y)^{l}(x - kz)^{n - k - l}\\
146 &= \sum_{k, l}(x + y)^{l}(-1)^{n - k - l}{n \choose k}{n - k \choose n - k - l}x(x - kz)^{n - l - 1}\\
147 &= \sum_{k, l}(x + y)^{l}(-1)^{n - k - l}{n \choose n - l}{n - l \choose k}x(x - kz)^{n - l - 1}\\
148 &= \sum_{l}{n \choose n - l}(x + y)^{l}\sum_{k}(-1)^{(n - l) - k}{n - l \choose k}x(x - kz)^{(n - l) - 1}.
149 \end{align*}
150 Using results from [[50]], we know that the inner sum is \(0\) unless \(n = l\), in which case the sum is \(0^{0} = 1\). Thus, above is equal to
151 \begin{align*}
152 &\quad\sum_{l = n}{n \choose n - l}(x + y)^{l}0^{0}\\
153 &= (x + y)^{n}.
154 \end{align*}
155
156 ***** DONE 52
157 CLOSED: [2021-01-03 Sun 18:26]
158 Setting \(n = x = -1, y = z = 1\), we have \((x + y)^{n} = (-1 + 1)^{-1} = 0\). However, applying (19), the RHS of (16) gives
159 \begin{align*}
160 &\quad\sum_{k}{n \choose k}x(x - kz)^{k - 1}(y + kz)^{n - k}\\
161 &= \sum_{k}{-1 \choose k}(-1)(-1 - k)^{k - 1}(1 + k)^{-1 - k}\\
162 &= \sum_{k}(-1)^{-k}{k \choose 0}(-1)(-1 - k)^{k - 1}(1 + k)^{-1 - k}\\
163 &= \sum_{k}(-1)^{1 - k}(-1 - k)^{k - 1}(1 + k)^{-1 - k}\\
164 &= \sum_{k}(1 + k)^{k - 1}(1 + k)^{-1 - k}\\
165 &= \sum_{k}(1 + k)^{-2},
166 \end{align*}
167 which doesn't converge due to \(k = -1\) term.
168
169 ***** INACTIVE 58
170 ***** INACTIVE 61
171 ***** INACTIVE 64
172 ***** INACTIVE 65
173 **** 1.2.7
174 Euler's constant, Riemann's zeta function, Bernoulli number, oh my!
175 Check CMath 6.5.
176
177 Try integration by parts on
178 \begin{align*}
179 \int_{1}^{n}x^{m}\ln{x} \dd x
180 &= \frac{n^{m+1}}{m+1}(\ln{n} - \frac{1}{m+1}) + \frac{1}{(m+1)^{2}}
181 \end{align*}
182
183 ***** INACTIVE 3
184 ***** INACTIVE 7
185 ***** INACTIVE 6
186 ***** INACTIVE 10
187 Summation by parts.
188 **** 1.2.8
189 Books to checkout
190 - /The Book of Numbers/ by Conway and Guy
191 - /The 2nd Scientific American Book of Mathematical Puzzles and Diversions/ by Martin Gardner
192
193 Proof of (4) using matrix determinants is cool.
194
195 Proof of (17) first step:
196 We have
197 \begin{align*}
198 \sum_{k=0}^{n}F_{k}F_{n-k}
199 &= \sum_{k=0}^{n}\frac{1}{\sqrt{5}}(\phi^{k} - \hat{\phi}^{k})\frac{1}{\sqrt{5}}(\phi^{n-k} - \hat{\phi}^{n-k})\\
200 &= \frac{1}{5}\sum_{k=0}^{n}(\phi^{n} - \phi^{k}\hat{\phi}^{n-k} - \hat{\phi}^{k}\phi^{n-k} + \hat{\phi}^{n})\\
201 &= \frac{1}{5}((n + 1)(\phi^{n} + \hat{\phi}^{n}) - 2\sum_{k=0}^{n}\phi^{k}\hat{\phi}^{n-k})\\
202 &= \frac{1}{5}((n + 1)(\phi^{n} + \hat{\phi}^{n}) - 2\frac{1}{\phi - \hat{\phi}}(\phi^{n + 1} - \hat{\phi}^{n + 1}))\\
203 &= \frac{1}{5}((n + 1)(\phi^{n} + \hat{\phi}^{n}) - 2\frac{1}{\sqrt{5}}(\phi^{n + 1} - \hat{\phi}^{n + 1}))\\
204 &= \frac{1}{5}((n + 1)(\phi^{n} + \hat{\phi}^{n}) - 2F_{n + 1}).
205 \end{align*}
206
207 ***** INACTIVE 3
208
209 ***** DONE 11
210 CLOSED: [2021-01-26 Tue 21:40]
211 From
212 \begin{align*}
213 \phi\hat{\phi}
214 &= \frac{1}{2}(1 + \sqrt{5})\frac{1}{2}(1 - \sqrt{5})\\
215 &= \frac{1}{4}(1 - 5)\\
216 &= -1,
217 \end{align*}
218 we have
219 \begin{align*}
220 F_{n}\phi + F_{n - 1}
221 &= \frac{1}{\sqrt{5}}(\phi(\phi^{n} - \hat{\phi^{n}}) + (\phi^{n - 1} - \hat{\phi}^{n - 1}))\\
222 &= \frac{1}{\phi - \hat{\phi}}(\phi(\phi^{n} - \hat{\phi^{n}}) + (\phi^{n - 1} - \hat{\phi}^{n - 1}))\\
223 &= \phi \sum_{k=0}^{n - 1}\phi^{k}\hat{\phi}^{(n - 1) - k} + \sum_{k=0}^{n - 2}\phi^{k}\hat{\phi}^{(n - 2) - k}\\
224 &= \phi^{n} + (\phi\hat{\phi} + 1) \sum_{k=0}^{n - 2}\phi^{k}\hat{\phi}^{(n - 2) - k}\\
225 &= \phi^{n}.
226 \end{align*}
227 Similarly we have
228 \begin{align*}
229 F_{n}\hat{\phi} + F_{n - 1}
230 &= \frac{1}{\sqrt{5}}(\hat{\phi}(\phi^{n} - \hat{\phi^{n}}) + (\phi^{n - 1} - \hat{\phi}^{n - 1}))\\
231 &= \frac{1}{\phi - \hat{\phi}}(\hat{\phi}(\phi^{n} - \hat{\phi^{n}}) + (\phi^{n - 1} - \hat{\phi}^{n - 1}))\\
232 &= \hat{\phi} \sum_{k=0}^{n - 1}\hat{\phi}^{k}\phi^{(n - 1) - k} + \sum_{k=0}^{n - 2}\hat{\phi}^{k}\phi^{(n - 2) - k}\\
233 &= \hat{\phi}^{n} + (\phi\hat{\phi} + 1) \sum_{k=0}^{n - 2}\phi^{k}\hat{\phi}^{(n - 2) - k}\\
234 &= \phi^{n}.
235 \end{align*}
236
237 **** 1.2.9
238 The trick in (7) is cool: the \(\frac{1}{1-z} G(z)\) factor gives us generating function of sums for \(G(z)\). This also gives (18).
239
240 We get (20) by applying identity 1.2.6-(17):
241 \begin{align*}
242 \frac{1}{(1 - z)^{n + 1}}
243 &= (1 + (-z))^{-(n + 1)}\\
244 &= \sum_{k \geq 0}{-n - 1 \choose k}(-z)^{k}\\
245 &= \sum_{k \geq 0}(-1)^{k}{k - (k + n) - 1 \choose k}z^{k}\\
246 &= \sum_{k \geq 0}{k + n \choose k}z^{k}\\
247 &= \sum_{k \geq 0}{k + n \choose n}z^{k}.
248 \end{align*}
249
250 Proof for (21) is 1.2.6-25.
251
252 To get (25), apply (6) to (17) and (20):
253 \begin{align*}
254 \frac{1}{(1 - z)^{m + 1}}\ln(\frac{1}{1 - z})
255 &= \sum_{n \geq 1} z^{n}\sum_{k = 0}^{n}{m + k \choose m} \frac{1}{n - k}
256 \end{align*}
257
258 (36) is an application of (6) to \(n\) generating functions of form \([z^{m}]H_{n}(z) = x_{n}^{m}\). Note that we can rewire (6) as
259 \begin{align*}
260 c_{m}
261 &= \sum_{k = 0}^{m}a_{k}b_{m-k}\\
262 &= \sum_{k = 0}^{m}x_{1}^{k}x_{2}^{m-k}\\
263 &= \sum_{1 \leq j_{1} \leq \cdots \leq j_{m} \leq 2}x_{j_{1}}\cdots x_{j_{m}}\\
264 &= h_{m, n = 2}.
265 \end{align*}
266 By induction we can then prove that
267 \begin{align*}
268 h_{m, n + 1}
269 &= \sum_{k = 0}^{m}h_{k, n}x_{n + 1}^{m-k}\\
270 &= \sum_{k = 0}^{m}x_{n + 1}^{m-k}\sum_{1 \leq j_{1} \leq \cdots \leq j_{k} \leq n}x_{j_{1}}\cdots x_{j_{k}}\\
271 &= \sum_{k = 0}^{m}\sum_{1 \leq j_{1} \leq \cdots \leq j_{m} \leq n + 1}x_{j_{1}}\cdots x_{j_{m}}[\sum_{l = 1}^{m}[j_{l} = n + 1] = m - k]\\
272 &= \sum_{1 \leq j_{1} \leq \cdots \leq j_{m} \leq n + 1}x_{j_{1}}\cdots x_{j_{m}}.
273 \end{align*}
274 Alternatively, this can also from rewriting (9) with \(a_{jk} = x_{j}\).
275
276 In (38), note that
277 \begin{align*}
278 \E^{S_{k}z^{k} / k}
279 &= \sum_{l \geq 0} \frac{1}{l!}(S_{k}z^{k} / k)^{l}\\
280 &= \sum_{l \geq 0} \frac{1}{l!}S_{k}^{l}z^{lk}k^{l},
281 \end{align*}
282 which means if the \(l\)-th term is chosen, we contribute \(z^{lk}\) to the product, represented by the \(\sum_{i = 1}^{m}ik_{i} = m\) condition (so that for \(z^{m}\)'s coefficient, we get the correct exponent).
283
284 For (39), differentiate (37) to get
285 \begin{align*}
286 \frac{G'(z)}{G(z)}
287 &= \sum_{k \geq 1} S_{k}z^{k - 1}\\
288 &= \sum_{k \geq 0} S_{k + 1}z^{k}.
289 \end{align*}
290 Rearranging gives
291 \begin{align*}
292 G'(z)
293 &= \sum_{j \geq 0}(j + 1)h_{j + 1}z^{j}\\
294 &= \sum_{k \geq 0}S_{k + 1}z^{k}G(z)\\
295 &= \sum_{k \geq 0}S_{k + 1}z^{k}(\sum_{l \geq 0}h_{l}z^{l})\\
296 &= \sum_{j \geq 0}z^{j}\sum_{k, j \geq 0, k + l = j}S_{k + 1}h_{l}\\
297 &=\sum_{j \geq 0}z^{j}\sum_{k \geq 1}S_{k}h_{j - k},
298 \end{align*}
299 or
300 \begin{align*}
301 h_{n}
302 &= \frac{1}{n}\sum_{k \geq 1}S_{k}h_{(n - 1) - k}.
303 \end{align*}
304
305 ***** DONE 14
306 CLOSED: [2021-07-04 Sun 10:25]
307 Since \(\omega^{m} = 1\), we have
308 \begin{align*}
309 \omega^{k}
310 &= \omega^{k \mod m}.
311 \end{align*}
312 Starting from RHS of (13), we have
313 \begin{align*}
314 \frac{1}{m}\sum_{0 \leq k < m}\omega^{-kr}G(\omega^{k}z)
315 &= \frac{1}{m}\sum_{n \geq 0}\sum_{0 \leq k < m}\omega^{-kr}a_{n}\omega^{kn}z^{n}\\
316 &= \frac{1}{m}\sum_{n \geq 0}a_{n}z^{n}\sum_{0 \leq k < m}\omega^{k(n-r)}\\
317 &= \frac{1}{m}\sum_{n \geq 0}a_{n}z^{n}\sum_{0 \leq k < m}\omega^{k((n-r) \mod m)}.
318 \end{align*}
319 If \(n \mod m = r\), then \((n - r) \mod m = 0\) and
320 \begin{align*}
321 \sum_{0 \leq k < m}\omega^{k((n-r) \mod m)}
322 &= \sum_{0 \leq k < m}\omega^{0}\\
323 &= m.
324 \end{align*}
325 If \(n \mod m \neq r\), let \(l = (n - r) \mod m \in [1, m)\), then we have
326 \begin{align*}
327 \sum_{0 \leq k < m}\omega^{kl}
328 &= \frac{1 - (\omega^{l})^{m}}{1 - \omega^{l}}\\
329 &= \frac{1 - (\omega^{m})^{l}}{1 - \omega^{l}}\\
330 &= \frac{1 - 1^{l}}{1 - \omega^{l}}\\
331 &= 0.
332 \end{align*}
333 Thus, we have
334 \begin{align*}
335 \frac{1}{m}\sum_{n \geq 0}a_{n}z^{n}\sum_{0 \leq k < m}\omega^{k((n-r) \mod m)}
336 &= \frac{1}{m}\sum_{n \geq 0}a_{n}z^{n}m\rInd_{n \mod m = r}\\
337 &= \sum_{n \geq 0, n \mod m = r}a_{n}z^{n}.
338 \end{align*}
339
340 **** 1.2.10
341 Notation for (4) is a bit confusing at first. We scan from back to the front, so if \(x_{1}\) is the \(n\)-th (largest), we would make the last update there, leaving \(k - 1\) updates when we go from \(x_{n}\) to \(x_{2}\) (\(P_{(n - 1)(k - 1)}\)). If \(x_{1}\) is not the largest, we would have made all \(k\) updates before we go to it (\(P_{(n - 1)k}\)).
342
343 To get (7), we rewrite \(G_{n}(z)\) using (4):
344 \begin{align*}
345 G_{n}(z)
346 &= \sum_{k}p_{nk}z^{k}\\
347 &= \sum_{k}(\frac{1}{n}p_{(n - 1)(k - 1)} + \frac{n - 1}{n}p_{(n - 1)k})z^{k}\\
348 &= \frac{z}{n} \sum_{k}p_{(n - 1)(k - 1)}z^{k - 1} + \frac{n - 1}{n}\sum_{k}p_{(n - 1)k}z^{k}\\
349 &= \frac{z}{n} G_{n - 1}(z) + \frac{n - 1}{n}G_{n - 1}(z)\\
350 &= \frac{z + n - 1}{n} G_{n - 1}(z).
351 \end{align*}
352 Similarly applying this to (17) we get
353 \begin{align*}
354 G_{n}(z)
355 &= \sum_{k}p_{nk}z^{k}\\
356 &= \sum_{k}(pp_{(n - 1)(k - 1)} + q p_{(n - 1)k})z^{k}\\
357 &= pz\sum_{k}pp_{(n - 1)(k - 1)}z^{k - 1} + q \sum_{k}p_{(n - 1)k}z^{k}\\
358 &= (q + pz)G_{n - 1}(z).
359 \end{align*}
360
361 Taylor's expansion for (20) reads
362 \begin{align*}
363 G(1 + z)
364 &= \frac{1}{n} \frac{(1 + z)^{n + 1} - 1 - z}{z}\\
365 &= \frac{1}{n} \frac{\sum_{k = 0}^{n + 1}{n + 1\choose k}z^{k} - 1 - z}{z}\\
366 &= \frac{1}{n} (\sum_{k = 1}^{n + 1}{n + 1\choose k}z^{k - 1} - 1)\\
367 &= \frac{1}{n} (n + \sum_{k = 2}^{n + 1}{n + 1\choose k}z^{k - 1})\\
368 &= 1 + \frac{1}{n}\sum_{k = 1}^{n}{n + 1\choose k + 1}z^{k}\\
369 &= 1 + \frac{1}{n}{n + 1\choose 2}z + \frac{1}{n}{n + 1 \choose 3}z^{2} + \cdots\\
370 &= 1 + \frac{n + 1}{2}z + \frac{(n + 1)(n - 1)}{6}z^{2} + \cdots.
371 \end{align*}
372
373 Didn't realize that \(\ev[X]\) can be read as expected value of \([X]\). Guess it does make sense to use \(\ev(X)\) or \(\ev X\) then.
374
375 ***** DONE 2
376 CLOSED: [2021-10-09 Sat 07:38]
377 Since
378 \begin{align*}
379 G''(z)
380 &= \sum_{k}k(k - 1)p_{k}z^{k - 1}\\
381 &= \sum_{k}k^{2}p_{k}z^{k - 1} - \sum_{k}kp_{k}z^{k - 1}\\
382 &= \sum_{k}k^{2}p_{k}z^{k - 1} - G'(z),
383 \end{align*}
384 it's easy to see that
385 \begin{align*}
386 \var(G)
387 &= \sum_{k}k^{2}p_{k} - (\sum_{k}kp_{k})^{2}\\
388 &= G''(1) + G'(1) - (G'(1))^{2}.
389 \end{align*}
390
391 ***** INACTIVE 13
392 ***** INACTIVE 14
393 ***** INACTIVE 21
394 ***** INACTIVE 22
395 ***** INACTIVE 23
396 **** 1.2.11.1
397 (10) seems useful. Also note the customary meaning of \(z\) being in the neighborhood of \(0\).
398 ***** INACTIVE 8
399 ***** INACTIVE 11
400 ***** INACTIVE 12
401 **** 1.2.11.2
402 To get (2), note that in \([k, k + 1)\), \(\{x\} = x - k\):
403 \begin{align*}
404 \int_{k}^{k + 1}(\{x\} - \frac{1}{2})f'(x)\dd x
405 &= (\{x\} - \frac{1}{2})f(x)|_{x = k}^{k + 1} - \int_{k}^{k + 1}f(x) \dd (\{x\} - \frac{1}{2})\\
406 &= (x - k - \frac{1}{2})f(x)|_{x = k}^{k + 1} - \int_{k}^{k + 1}f(x) \dd x.
407 \end{align*}
408
409
410 By no discontinuities it meant that \(B_{m}(\{x\}) = B_{m}\) at all \([t, t+1]\) boundary points with \(t \geq 1\). The integration by parts results can then be simplified as:
411 \begin{align*}
412 \frac{1}{m!} \int_{1}^{n}B_{m}(\{x\})f^{(m)}(x)\dd x
413 &= \frac{1}{(m + 1)!} \int_{1}^{n}f^{(m)}(x)\dd B_{m + 1}(\{x\})\\
414 &= \frac{1}{(m + 1)!} (B_{m + 1}(\{x\})f^{m}(x))|_{x = 1}^{n} - \frac{1}{(m + 1)!} \int_{1}^{n}B_{m + 1}(\{x\}) f^{(m + 1)}(x)\dd x\\
415 &= \frac{B_{m + 1}}{(m + 1)!}(f^{m}(n) - f^{m}(1)) - \frac{1}{(m + 1)!} \int_{1}^{n}B_{m + 1}(\{x\}) f^{(m + 1)}(x)\dd x.
416 \end{align*}
417
418
419 See Concrete Mathematics 9.5 for proof of (12). Also note how we get Stiring's approximation and Euler's constant from (10)!
420
421 \(\E^{\sigma} = \sqrt{2\pi}\) is another interesting fact. The most common form of Stirling's approximation is probably with \(m = 1\)
422 \begin{align*}
423 \ln n!
424 &= (n + \frac{1}{2})\ln n - n + \sigma + O(\frac{1}{n}),\\
425 n!
426 &= \E^{\sigma}\sqrt{n}(\frac{n}{\E})^{n} + O(\frac{1}{n})\\
427 &= \sqrt{2\pi n}(\frac{n}{\E})^{n} + O(\frac{1}{n}).
428 \end{align*}
429
430 ***** DONE 1
431 CLOSED: [2021-10-09 Sat 09:12]
432 To get (7), multiply (4) by \(\E^{z} - 1\):
433 \begin{align*}
434 z
435 &= \sum_{n \geq 0}\delta_{n1}z^{n}\\
436 &= (\E^{z} - 1)\sum_{k \geq 0}\frac{B_{k}z^{k}}{k!}\\
437 &= (\sum_{j \geq 0}\frac{z^{j}}{j!} - 1)\sum_{k \geq 0}\frac{B_{k}z^{k}}{k!}\\
438 &= \sum_{n \geq 0}z^{n}(\sum_{0 \leq k \leq n}\frac{B_{k}}{k!(n-k)!} - \frac{B_{n}}{n!}).
439 \end{align*}
440 Equating the coefficients we get
441 \begin{align*}
442 \sum_{0 \leq k \leq n}\frac{B_{k}}{k!(n-k)!} - \frac{B_{n}}{n!}
443 &= \delta_{n1},\\
444 \sum_{k}{n\choose k}B_{k}
445 &= B_{n} + n!\denta_{n1}\\
446 &= B_{n} + 1!\denta_{n1}\\
447 &= B_{n} + \denta_{n1}.
448 \end{align*}
449
450 ***** INACTIVE 3
451 ***** INACTIVE 5
452 ***** INACTIVE 6
453 **** 1.2.11.3
454
455 Note that
456 \begin{align*}
457 \Gamm(x + 1)
458 &= \int_{0}^{\infty}\E^{-t}t^{x}\dd t,
459 \end{align*}
460 thus the following
461 \begin{align*}
462 \frac{1}{\Gamma(x + 1)}\int_{0}^{x + y}\E^{-t}t^{x}\dd t
463 &= \frac{1}{\Gamma(x + 1)}(\Gamma(x + 1) - \int_{x}^{\infty}\E^{-t}t^{x}\dd t + \int_{x}^{x + y}\E^{-t}t^{x}\dd t)\\
464 &= 1 - \frac{1}{\Gamma(x + 1)}\int_{x}^{\infty}\E^{-t}t^{x}\dd t + \frac{1}{\Gamma(x + 1)}\int_{x}^{x + y}\E^{-t}t^{x}\dd t).
465 \end{align*}
466
467 For the expansion after (11), we can write
468 \begin{align*}
469 1 - \frac{2}{3}u + \frac{1}{2}u^{2} - \frac{2}{5}u^{3} + \cdots
470 &= (\sum_{i = 0}^{\infty}a_{i}u^{i})^{2}\\
471 &= \sum_{i = 0}^{\infity}u^{i}\sum_{j = 0}^{i}a_{j}a_{i-j}.
472 \end{align*}
473 We can then solve the first few terms
474 \begin{align*}
475 \begin{cases}
476 1
477 &= a_{0}^{2},\\
478 -\frac{2}{3}
479 &= 2a_{0}a_{1}\\
480 \frac{1}{2}
481 &= 2a_{0}a_{2} + a_{1}^{2},\\
482 -\frac{2}{5}
483 &= 2a_{0}a_{3} + 2a_{1}a_{2},\\
484 \cdots,
485 \end{cases}
486 \end{align*}
487 and we get
488 \begin{align*}
489 a_{0}
490 &= \sqrt(1)\\
491 &= 1,\\
492 a_{1}
493 &= \frac{-\frac{2}{3}}{2a_{0}}\\
494 &= -\frac{1}{3},\\
495 a_{2}
496 &= \frac{\frac{1}{2} - a_{1}^{2}}{2a_{0}}\\
497 &= \frac{1}{2}(\frac{1}{2} - \frac{1}{9})\\
498 &= \frac{7}{36},\\
499 a_{3}
500 &= \frac{1}{a_{0}}(-\frac{1}{5} + a_{1}a_{2})\\
501 &= -\frac{1}{5} - (-\frac{1}{3})\frac{7}{36}\\
502 &= - \frac{73}{540},\\
503 &\cdots.
504 \end{align*}
505 To express \(u\) in \(w\), we just try to cancel one term at a time using the polynomial form, which would probably go something like the above, and there's probably some easier pattern that allows us to write things out easier. Guess we'll find out in 4.7.
506
507 Change of variable in (14) is \(q = xv\). Recall that
508 \begin{align*}
509 \Gamma(1 + n)
510 &= n!,\\
511 \Gamma(\frac{1}{2} + n)
512 &= \frac{(2n)!}{n^{n}n!}\sqrt(\pi),
513 \end{align*}
514 for (15).
515
516 For Taylor expansion after (16), we only need to keep terms up to \(x^{-2}\):
517 \begin{align*}
518 \exp(\frac{-u^{2}}{2x} + \frac{u^{3}}{3x^{2}} + O(x^{-3}))
519 &= 1 + (\frac{-u^{2}}{2x} + \frac{u^{3}}{3x^{2}} + O(x^{-3})) + \frac{1}{2}(\frac{-u^{2}}{2x} + \frac{u^{3}}{3x^{2}} + O(x^{-3}))^{2} + O(x^{-3})\\
520 &= 1 - \frac{u^{2}}{2x} + \frac{u^{3}}{3x^{2}} + \frac{u^{4}}{8x^{2}} + O(x^{-3}).
521 \end{align*}
522 Then we can just do the integration term by term
523 \begin{align*}
524 \int_{0}^{y}\E^{-u}(1 + \frac{u}{x})^{x}\dd u
525 &= \int_{0}^{y}(1 - \frac{u^{2}}{2x} + \frac{u^{4}}{8x^{2}} + \frac{u^{3}}{3x^{2}} + O(x^{-3}))\dd u\\
526 &= (u - \frac{u^{3}}{6x} + \frac{u^{5}}{40x^{2}} + \frac{u^{4}}{12x^{2}} + uO(x^{-3}))|_{u = 0}^{y}\\
527 &= y - \frac{y^{3}}{6}x + (\frac{y^{5}}{40} + \frac{y^{4}}{12})x^{-2} + O(x^{-3}).
528 \end{align*}
529
530 For (18) we use Stirling's approximation in exponential form (above 1.2.11.2 (19)).
531
532 Third term in (21) gets absorbed by \(O(n^{n}\E^{-n})\) in (22).
533
534 Try Ramanujan's treatment for \(Q(n)\)!
535
536 ***** 2
537 ***** 3
538 ***** 4
539 ***** 5
540 ***** 6
541 ***** 14
542 ***** 19
543 Watson's lemma! o7
544 ***** 20
545 ** INACTIVE 1.3'
546 Reading the Fascicle 1 instead for 1.3.1 - 1.3.2. For 1.3.3 reading the original + program listing in the MMIX Supplement.
547 *** 1.3.1'
548 Note how in (6) the load behavior is defined: when the load width increases, we can include bytes before or after A. Also note the sign behavior.
549
550 Why does it overflow in =STB/STW=? Because neither a byte (8 bits) or a wide (16 bits) can represent the value \(-65536 = -2^{16}\), while a tetra (32 bits) or a octa (64 bits) can in signed mode.
551
552 Note the use of rH and rD in unsigned arithmetic.
553
554 The bitwise operations are indeed bitwise! Bytewise operations feels like AVX.
555
556 For floating point numbers, notice that the normal case includes an implicit \(1\cdot 2^{E-1023}\) (probably because 0 has special representation). Also note that there are actually \(2^{52} - 1\) possible representations for NaN (which seems to be used as a way to sneak in extra information).
557
558 The \(\pi\), \(\mu\), and \(v\) denotes the time taken for each operation.
559
560 **** 32
561 **** 33
562 **** 34
563 **** 35
564 **** 36
565 **** 37
566 **** 57
567
568 ** INACTIVE 1.4'
569 Reading Fascicle 1 for 1.4.1 - 1.4.3.
570 *** 1.4.2
571 **** 21
572 1.3.1
573 ** TODO Chapter 2: Information structures
574 **** 2.3.4.4
575 ***** INACTIVE 29
576 1.2.9
577
578 ** INACTIVE Chapter 4
579 *** 4.7
580 **** 22
581 1.2.9