# notes-TAOCP

Notes for /The Art of Computer Programming/

git clone git://git.shimmy1996.com/notes-TAOCP.git
commit 036a681a651ee1d742f166d1591f6de55777a8c2
Author: Shimmy Xu <shimmy.xu@shimmy1996.com>
Date:   Sun,  4 Apr 2021 19:53:49 -0500

Initial commit

Add Volume 1 notes so far

Diffstat:

1 file changed, 221 insertions(+), 0 deletions(-)
@@ -0,0 +1,221 @@
+#+STARTUP: logdone
+
+* TODO The Art of Computer Programming Volume 1: Fundamental Algorithms
+** TODO Chapter 1: Basic concepts
+*** TODO 1.1 Algorithms
+:LOGBOOK:
+CLOCK: [2020-12-28 Mon 19:54]--[2020-12-28 Mon 20:26] =>  0:32
+:END:
+*** TODO 1.2 Mathematical Preliminaries
+:LOGBOOK:
+CLOCK: [2021-01-03 Sun 16:03]--[2021-01-03 Sun 18:28] =>  2:25
+CLOCK: [2020-12-30 Tue 20:50]--[2020-12-30 Wed 21:20] =>  0:30
+CLOCK: [2020-12-29 Tue 20:11]--[2020-12-29 Wed 21:30] =>  1:19
+CLOCK: [2020-12-28 Mon 20:27]--[2020-12-28 Mon 21:29] =>  1:02
+:END:
+**** 1.2.1
+***** DONE 1
+CLOSED: [2021-01-10 Sun 06:35]
+Change all occurrences of $$P(1)$$ to $$P(0)$$. In I1, set $$k \left 0$$.
+***** DONE 2
+CLOSED: [2021-01-10 Sun 06:35]
+When $$n = 1$$, the quantity $$b = a^(n-2)/(n-1)$$ is not defined due to division by zero.
+***** INACTIVE 3
+***** TODO 4
+***** INACTIVE 5
+***** DONE 6
+CLOSED: [2021-01-10 Sun 06:35]
+$$a'm + b'n = c$$ is trivial as it's $$am + bn = d$$ after rename in E4.
+Given Eqs. (6) and $$c = qd + r$$, we also have:
+\begin{align*}
+  r
+  &= c - qd\\
+  &= (a'm + b'n) - q(am + bn)\\
+  &= (a' - qa)m + (b' - qb)n.
+\end{align*}
+After E4, this equality becomes $$am + bn = d$$.
+**** 1.2.2
+Never thought about the not ending in infinitely many 9s part.
+**** 1.2.3
+I knew Kronecker delta, but not Iverson's convention.
+**** 1.2.4
+The construction of $$x \mod y$$ here is well defined when $$y < 0$$.
+***** DONE 35
+CLOSED: [2021-01-10 Sun 06:34]
+Note that $$0 \leq x - \floor{x} < 1$$, so we have $$x \mod n = \floor{x} \mod n + (x - \floor{x})$$.
+\begin{align*}
+  n \floor{(x + m) / n}
+  &= (x - m) - (x + m) \mod m\\
+  &= (x - m) - (\floor{x + m} \mod m + (x + m - \floor{x + m}))\\
+  &= (\floor{x} - m) - (\floor{x} + m) \mod m\\
+  &= n \floor((\floor{x} + m) / n),\\
+  \floor{(x + m) / n}
+  &= \floor((\floor{x} + m) / n).
+\end{align*}
+
+**** 1.2.5
+Method II conditions on the last number being $$k$$, effectively.
+Ah Stirling's appproximation.
+
+2nd equality in (20): just a sign trick.
+
+**** 1.2.6
+Note how the $$r$$ in $${r \choose k} = \frac{r^{\underline{k}}}{k!}$$ is real.
+
+$$n + 1$$ point equality proof for $$n$$-th order polynomials is a neat argument.
+
+(9) is again, conditioning on last element.
+
+Never seen E before, related proof for sum of squares is cool.
+
+For binomial theorem, when $$r < 0$$, where does the $$\abs{x/y} < 1$$ restriction comes from?
+As now the series is infinite, and for
+\begin{align*}
+  \sum_{k}{r \choose k}x^{k}y^{r-k}
+  &= y^{r}\sum_{k}{r \choose k}(\frac{x}{y})^{k},
+\end{align*}
+that's a necessary condition for convergence.
+
+Abel's (16) is interesting.
+
+Proof for (17):
+\begin{align*}
+  {r \choose k}
+  &= \frac{r(r - 1)\dots(r - k + 1)}{k!}\\
+  &= (-1)^{k}\frac{(-r)(1 - r)\dots(k - r - 1)}{k!}\\
+  &= (-1)^{k}\frac{(k - r - 1)\dots((k - r - 1) - k)((k - r - 1) - (k - 1))}{k!}\\
+  &= (-1)^{k}{k - r - 1 \choose k}.
+\end{align*}
+
+Proof for (35):
+\begin{align*}
+  \sum_{k}{r \choose k}{s - kt \choose r}(-1)^{k}
+  &= \sum_{k}{r \choose k}\frac{(s - kt)(s - kt - 1)\dots(s - kt - r + 1)}{r!}(-1)^{k}\\
+  &= \sum_{k}{r \choose k}\frac{(kt - s)(kt - s + 1)\dots(kt - s + r - 1)}{r!}(-1)^{r - k}(-1)^{2k}\\
+  &= \frac{1}{r!}\sum_{k}{r \choose k}(-1)^{r - k}(tk - s)(tk - s + 1)\dots(tk - s + r - 1)\\
+  &= \frac{1}{r!}\sum_{k}{r \choose k}(-1)^{r - k}(b_{0} + b_{1}tk + \cdots + t^{r}k^{r}),
+\end{align*}
+for some $$b_{i}$$. Applying (34) gives the answer $$t^{r}$$.
+
+Try to prove (37) and (38).
+
+Check /Concrete Math/ 5.8 for Gosper-Zeilberger algorithm and 6.1 for Stirling numbers.
+
+***** INACTIVE 36
+***** INACTIVE 40
+***** INACTIVE 41
+***** INACTIVE 42
+***** INACTIVE 43
+***** INACTIVE 44
+***** INACTIVE 45
+***** DONE 50
+CLOSED: [2021-01-03 Sun 17:02]
+When $$x + y = 0$$, we have by applying (17) and that $$n - k > -1 - k$$,
+\begin{align*}
+  &\quad\sum_{k}{n \choose k}x(x - kz)^{k - 1}(y + kz)^{n - k}\\
+  &= \sum_{k}{n \choose k}x(x - kz)^{k - 1}(-x + kz)^{n - k}\\
+  &= \sum_{k}(-1)^{n - k}{n \choose k}x(x - kz)^{n - 1}\\
+  &= \sum_{k}(-1)^{n - k}{n \choose n - k}x(x - kz)^{n - 1}\\
+  &= \sum_{k}{-1 - k \choose n - k}x(x - kz)^{n - 1}\\
+  &= 0\\
+  &= (x + y)^{n}.
+\end{align*}
+
+***** DONE 51
+CLOSED: [2021-01-03 Sun 17:52]
+Writing $$y = (x + y) - x$$, we have by (20),
+\begin{align*}
+  &\quad\sum_{k}{n \choose k}x(x - kz)^{k - 1}((x + y) - x + kz)^{n - k}\\
+  &= \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}\\
+  &= \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}\\
+  &= \sum_{k, l}(x + y)^{l}(-1)^{n - k - l}{n \choose n - l}{n - l \choose k}x(x - kz)^{n - l - 1}\\
+  &= \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}.
+\end{align*}
+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
+\begin{align*}
+  &\quad\sum_{l = n}{n \choose n - l}(x + y)^{l}0^{0}\\
+  &= (x + y)^{n}.
+\end{align*}
+
+***** DONE 52
+CLOSED: [2021-01-03 Sun 18:26]
+Setting $$n = x = -1, y = z = 1$$, we have $$(x + y)^{n} = (-1 + 1)^{-1} = 0$$. However, applying (19), the RHS of (16) gives
+\begin{align*}
+  &\quad\sum_{k}{n \choose k}x(x - kz)^{k - 1}(y + kz)^{n - k}\\
+  &= \sum_{k}{-1 \choose k}(-1)(-1 - k)^{k - 1}(1 + k)^{-1 - k}\\
+  &= \sum_{k}(-1)^{-k}{k \choose 0}(-1)(-1 - k)^{k - 1}(1 + k)^{-1 - k}\\
+  &= \sum_{k}(-1)^{1 - k}(-1 - k)^{k - 1}(1 + k)^{-1 - k}\\
+  &= \sum_{k}(1 + k)^{k - 1}(1 + k)^{-1 - k}\\
+  &= \sum_{k}(1 + k)^{-2},
+\end{align*}
+which doesn't converge due to $$k = -1$$ term.
+
+***** INACTIVE 58
+***** INACTIVE 61
+***** INACTIVE 64
+***** INACTIVE 65
+**** 1.2.7
+Euler's constant, Riemann's zeta function, Bernoulli number, oh my!
+Check CMath 6.5.
+
+Try integration by parts on
+\begin{align*}
+  \int_{1}^{n}x^{m}\ln{x} \dd x
+  &= \frac{n^{m+1}}{m+1}(\ln{n} - \frac{1}{m+1}) + \frac{1}{(m+1)^{2}}
+\end{align*}
+
+***** INACTIVE 3
+***** INACTIVE 7
+***** INACTIVE 6
+***** INACTIVE 10
+Summation by parts.
+**** 1.2.8
+Books to checkout
+- /The Book of Numbers/ by Conway and Guy
+- /The  2nd Scientific American Book of Mathematical Puzzles and Diversions/ by Martin Gardner
+
+Proof of (4) using matrix determinants is cool.
+
+Proof of (17) first step:
+We have
+\begin{align*}
+  \sum_{k=0}^{n}F_{k}F_{n-k}
+  &= \sum_{k=0}^{n}\frac{1}{\sqrt{5}}(\phi^{k} - \hat{\phi}^{k})\frac{1}{\sqrt{5}}(\phi^{n-k} - \hat{\phi}^{n-k})\\
+  &= \frac{1}{5}\sum_{k=0}^{n}(\phi^{n} - \phi^{k}\hat{\phi}^{n-k} - \hat{\phi}^{k}\phi^{n-k} + \hat{\phi}^{n})\\
+  &= \frac{1}{5}((n + 1)(\phi^{n} + \hat{\phi}^{n}) - 2\sum_{k=0}^{n}\phi^{k}\hat{\phi}^{n-k})\\
+  &= \frac{1}{5}((n + 1)(\phi^{n} + \hat{\phi}^{n}) - 2\frac{1}{\phi - \hat{\phi}}(\phi^{n + 1} - \hat{\phi}^{n + 1}))\\
+  &= \frac{1}{5}((n + 1)(\phi^{n} + \hat{\phi}^{n}) - 2\frac{1}{\sqrt{5}}(\phi^{n + 1} - \hat{\phi}^{n + 1}))\\
+  &= \frac{1}{5}((n + 1)(\phi^{n} + \hat{\phi}^{n}) - 2F_{n + 1}).
+\end{align*}
+
+***** INACTIVE 3
+
+***** DONE 11
+CLOSED: [2021-01-26 Tue 21:40]
+From
+\begin{align*}
+  \phi\hat{\phi}
+  &= \frac{1}{2}(1 + \sqrt{5})\frac{1}{2}(1 - \sqrt{5})\\
+  &= \frac{1}{4}(1 - 5)\\
+  &= -1,
+\end{align*}
+we have
+\begin{align*}
+  F_{n}\phi + F_{n - 1}
+  &= \frac{1}{\sqrt{5}}(\phi(\phi^{n} - \hat{\phi^{n}}) + (\phi^{n - 1} - \hat{\phi}^{n - 1}))\\
+  &= \frac{1}{\phi - \hat{\phi}}(\phi(\phi^{n} - \hat{\phi^{n}}) + (\phi^{n - 1} - \hat{\phi}^{n - 1}))\\
+  &= \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}\\
+  &= \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
+\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}))\\
+  &= \frac{1}{\phi - \hat{\phi}}(\hat{\phi}(\phi^{n} - \hat{\phi^{n}}) + (\phi^{n - 1} - \hat{\phi}^{n - 1}))\\
+  &= \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}\\
+  &= \hat{\phi}^{n} + (\phi\hat{\phi} + 1) \sum_{k=0}^{n - 2}\phi^{k}\hat{\phi}^{(n - 2) - k}\\
+  &= \phi^{n}.
+\end{align*}
+
+** TODO Chapter 2: Information structures