notes-TAOCP

Notes for /The Art of Computer Programming/

git clone git://git.shimmy1996.com/notes-TAOCP.git

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