# notes-TAOCP

Notes for /The Art of Computer Programming/

git clone git://git.shimmy1996.com/notes-TAOCP.git
commit 70b027f318947199a3ac6a544669a0792f579c13
parent 7805488297100e33233a99a4602e26b60a504d14
Author: Shimmy Xu <shimmy.xu@shimmy1996.com>
Date:   Sun,  4 Jul 2021 10:27:39 -0500

Diffstat:

1 file changed, 118 insertions(+), 1 deletion(-)
@@ -6,6 +6,7 @@
#+INCLUDE: "~/.emacs.d/static/math_macros.sty" src latex-macros
#+Options: toc:nil num:t
#+STARTUP: logdone
+#+TODO: INACTIVE TODO | DONE

* TODO The Art of Computer Programming Volume 1: Fundamental Algorithms
** TODO Chapter 1: Basic concepts
@@ -45,6 +46,9 @@ After E4, this equality becomes $$am + bn = d$$.
Never thought about the not ending in infinitely many 9s part.
**** 1.2.3
I knew Kronecker delta, but not Iverson's convention.
+***** 29
+1.2.9
+
**** 1.2.4
The construction of $$x \mod y$$ here is well defined when $$y < 0$$.
***** DONE 35
@@ -108,6 +112,8 @@ Try to prove (37) and (38).

Check /Concrete Math/ 5.8 for Gosper-Zeilberger algorithm and 6.1 for Stirling numbers.

+***** TODO 25
+
***** INACTIVE 36
***** INACTIVE 40
***** INACTIVE 41
@@ -215,7 +221,7 @@ we have
&= \phi^{n} + (\phi\hat{\phi} + 1) \sum_{k=0}^{n - 2}\phi^{k}\hat{\phi}^{(n - 2) - k}\\
&= \phi^{n}.
\end{align*}
-Similarily we have
+Similarly we have
\begin{align*}
F_{n}\hat{\phi} + F_{n - 1}
&= \frac{1}{\sqrt{5}}(\hat{\phi}(\phi^{n} - \hat{\phi^{n}}) + (\phi^{n - 1} - \hat{\phi}^{n - 1}))\\
@@ -225,4 +231,115 @@ Similarily we have
&= \phi^{n}.
\end{align*}

+**** 1.2.9
+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).
+
+We get (20) by applying identity 1.2.6-(17):
+\begin{align*}
+  \frac{1}{(1 - z)^{n + 1}}
+  &= (1 + (-z))^{-(n + 1)}\\
+  &= \sum_{k \geq 0}{-n - 1 \choose k}(-z)^{k}\\
+  &= \sum_{k \geq 0}(-1)^{k}{k - (k + n) - 1 \choose k}z^{k}\\
+  &= \sum_{k \geq 0}{k + n \choose k}z^{k}\\
+  &= \sum_{k \geq 0}{k + n \choose n}z^{k}.
+\end{align*}
+
+Proof for (21) is 1.2.6-25.
+
+To get (25), apply (6) to (17) and (20):
+\begin{align*}
+  \frac{1}{(1 - z)^{m + 1}}\ln(\frac{1}{1 - z})
+  &= \sum_{n \geq 1} z^{n}\sum_{k = 0}^{n}{m + k \choose m} \frac{1}{n - k}
+\end{align*}
+
+(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
+\begin{align*}
+  c_{m}
+  &= \sum_{k = 0}^{m}a_{k}b_{m-k}\\
+  &= \sum_{k = 0}^{m}x_{1}^{k}x_{2}^{m-k}\\
+  &= \sum_{1 \leq j_{1} \leq \cdots \leq j_{m} \leq 2}x_{j_{1}}\cdots x_{j_{m}}\\
+  &= h_{m, n = 2}.
+\end{align*}
+By induction we can then prove that
+\begin{align*}
+h_{m, n + 1}
+&= \sum_{k = 0}^{m}h_{k, n}x_{n + 1}^{m-k}\\
+&= \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}}\\
+&= \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]\\
+&= \sum_{1 \leq j_{1} \leq \cdots \leq j_{m} \leq n + 1}x_{j_{1}}\cdots x_{j_{m}}.
+\end{align*}
+Alternatively, this can also from rewriting (9) with $$a_{jk} = x_{j}$$.
+
+In (38), note that
+\begin{align*}
+  e^{S_{k}z^{k} / k}
+  &= \sum_{l \geq 0} \frac{1}{l!}(S_{k}z^{k} / k)^{l}\\
+  &= \sum_{l \geq 0} \frac{1}{l!}S_{k}^{l}z^{lk}k^{l},
+\end{align*}
+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).
+
+For (39), differentiate (37) to get
+\begin{align*}
+  \frac{G'(z)}{G(z)}
+  &= \sum_{k \geq 1} S_{k}z^{k - 1}\\
+  &= \sum_{k \geq 0} S_{k + 1}z^{k}.
+\end{align*}
+Rearranging gives
+\begin{align*}
+  G'(z)
+  &= \sum_{j \geq 0}(j + 1)h_{j + 1}z^{j}\\
+  &= \sum_{k \geq 0}S_{k + 1}z^{k}G(z)\\
+  &= \sum_{k \geq 0}S_{k + 1}z^{k}(\sum_{l \geq 0}h_{l}z^{l})\\
+  &= \sum_{j \geq 0}z^{j}\sum_{k, j \geq 0, k + l = j}S_{k + 1}h_{l}\\
+  &=\sum_{j \geq 0}z^{j}\sum_{k \geq 1}S_{k}h_{j - k},
+\end{align*}
+or
+\begin{align*}
+  h_{n}
+  &= \frac{1}{n}\sum_{k \geq 1}S_{k}h_{(n - 1) - k}.
+\end{align*}
+
+***** DONE 14
+CLOSED: [2021-07-04 Sun 10:25]
+Since $$\omega^{m} = 1$$, we have
+\begin{align*}
+  \omega^{k}
+  &= \omega^{k \mod m}.
+\end{align*}
+Starting from RHS of (13), we have
+\begin{align*}
+  \frac{1}{m}\sum_{0 \leq k < m}\omega^{-kr}G(\omega^{k}z)
+  &= \frac{1}{m}\sum_{n \geq 0}\sum_{0 \leq k < m}\omega^{-kr}a_{n}\omega^{kn}z^{n}\\
+  &= \frac{1}{m}\sum_{n \geq 0}a_{n}z^{n}\sum_{0 \leq k < m}\omega^{k(n-r)}\\
+  &= \frac{1}{m}\sum_{n \geq 0}a_{n}z^{n}\sum_{0 \leq k < m}\omega^{k((n-r) \mod m)}.
+\end{align*}
+If $$n \mod m = r$$, then $$(n - r) \mod m = 0$$ and
+\begin{align*}
+  \sum_{0 \leq k < m}\omega^{k((n-r) \mod m)}
+  &= \sum_{0 \leq k < m}\omega^{0}\\
+  &= m.
+\end{align*}
+If $$n \mod m \neq r$$, let $$l = (n - r) \mod m \in [1, m)$$, then we have
+\begin{align*}
+  \sum_{0 \leq k < m}\omega^{kl}
+  &= \frac{1 - (\omega^{l})^{m}}{1 - \omega^{l}}\\
+  &= \frac{1 - (\omega^{m})^{l}}{1 - \omega^{l}}\\
+  &= \frac{1 - 1^{l}}{1 - \omega^{l}}\\
+  &= 0.
+\end{align*}
+Thus, we have
+\begin{align*}
+   \frac{1}{m}\sum_{n \geq 0}a_{n}z^{n}\sum_{0 \leq k < m}\omega^{k((n-r) \mod m)}
+  &= \frac{1}{m}\sum_{n \geq 0}a_{n}z^{n}m\rInd_{n \mod m = r}\\
+  &= \sum_{n \geq 0, n \mod m = r}a_{n}z^{n}.
+\end{align*}
+
** TODO Chapter 2: Information structures
+**** 2.3.4.4
+***** INACTIVE 29
+1.2.9
+
+** INACTIVE Chapter 4
+*** 4.7
+**** 22
+1.2.9