A.1-1

Find a simple formula for \(\sum_{k = 1}^n(2k - 1).\)

Sol’n

\[ \begin{align*} \sum_{k = 1}^n(2k - 1) & = 2 \sum_{k = 1}^n k - \sum_{k = 1}^n 1 \\ & = 2 \left(\frac{n(n - 1)}{2}\right) - n \\ & = n(n - 2). \end{align*} \]

A.1-2 ⭑

Show that \(\sum_{k = 1}^n 1/(2k - 1) = \ln(\sqrt n) + O(1)\) by manipulating the harmonic series.

Sol’n

In this section, we are given that \(\sum_{k = 1}^n 1/k = \ln n + O(1).\) Then we are given that there is some \(c, N,\) such that for any \(n \ge N,\)

\[ \sum_{k = 1}^n \frac {1}{k} \le \ln n + c. \]

From which it follows that for any \(n \ge N,\)

\[ \begin{align*} \sum_{k = 1}^n \frac {1}{2k + 1} & < \sum_{k = 1}^n \frac {1}{2k} \\ & = \frac {1}{2} \sum_{k = 1}^n \frac {1}{k} \\ & \le \frac {1}{2} (\ln n + c) \\ & = \ln \left(\sqrt n \right) + c', \\ \end{align*} \]

where \(c' = c/2.\) Then, adding 1 to both sides, and taking \(c'' = c + 1,\) we have, as desired, for any \(n \ge N,\)

\[ \sum_{k = 1}^n \frac {1}{2k - 1} = \ln \left(\sqrt n \right) + c''. \]

A.1-3

Show that \(\sum_{k = 0}^\infty k^2 x^k = x(1 + x)/(1 - x)^3\) for \(0 < |x| < 1.\)

Sol’n

We are given that, for \(\|x\| < 1,\) we have

\[ \sum_{k = 0}^\infty k x^k = x\, (1 - x)^{-2}. \]

Applying the derivative to both sides, we have

\[ \begin{align*} \sum_{k = 0}^\infty k^2 x^{k - 1} & = (1 - x)^{-2} + x\, (1 - x)^{-3}\cdot(-2)\cdot(-1) \\ & = \frac {1}{(1 - x)^2} + \frac {2x}{(1 - x)^3} \\ & = \frac {1 + x}{(1 - x)^3}. \end{align*} \]

Multiplying both sides by \(x\) gives us the desired result.

A.1-4 ⭑

Show that \(\sum_{k = 1}^\infty (k - 1)/2^k = 0.\)

Sol’n

We get the desired result by plugging in \(x = 1/2\) into the following,

\[ \begin{align*} \sum_{k = 0}^\infty (k - 1) x^k & = \sum_{k = 0}^\infty k x^k - \sum_{k = 0}^\infty x^k \\ & = \frac {x}{(1 - x)^2} - \frac {1}{1 - x} \\ & = \frac {2x - 1}{(1 - x)^2}. \end{align*} \]

A.1-5 ⭑

Evaluate the sum \(\sum_{k = 1}^\infty (2k + 1) x^{2k}.\)

Sol’n

rough draft:

\[ \begin{align*} \sum_{k = 1}^\infty x^k & = \left(\sum_{k = 0}^\infty x^k\right) - 1 \\ & = \frac {1}{1 - x} - 1 \\ & = \frac {1 - (1 - x)}{1 - x} \\ & = \frac {x}{1 - x}. \end{align*} \]

Note that

\[ \sum_{k = 0}^n y^k = \frac {1}{1 - y}, \]

then for \(y = x^2\), we have

\[ \begin{align*} \sum_{k = 1}^n x^{2k + 1} & = x \cdot \sum_{k = 1}^\infty \left( x^2 \right)^k \\ & = x \frac {x^2}{1 - x^2} \\ & = \frac {x^3}{1 - x^2}. \end{align*} \]

\[ \begin{align*} \sum_{k = 1}^\infty (2k + 1) x^{2k} & = \frac {d}{dx} \left( \sum_{k = 1}^\infty\ x^{2k + 1} \right) \\ & = \frac {d}{dx} \left( \frac {x^3}{1 - x^2} \right) \\ & = \frac {3x^2}{1 - x^2} - \frac {x^3}{\left(1 - x^2\right)^2}\cdot(-2x) \\ & = \frac {3x^2 \left(1 - x^2\right) + 2x^4}{\left(1 - x^2\right)^2} \\ & = \frac {3x^2 - x^4}{\left(1 - x^2\right)^2} \\ \end{align*} \]

A.1-6

Prove that \(\sum_{k = 0}^n O(f_k(i)) = O(\sum_{k = 0}^n f_k(i))\) by using the linearity property of summations.

Sol’n

rough draft:

If \(g_k(i) \in O(f_k(i)),\) then there is some \(c_k, I_k\) such that for any \(i \ge I_k\), \(0 \le g_k(i) \le c_k \cdot f_k(i).\) Letting \(c = \max\\{c_k\\}\) and \(I = \max\\{I_k\\},\) then we have for any \(i \ge I,\)

\[ 0 \le \sum_{k = 0}^n g_k(i) \le c \cdot \sum_{k = 0}^n f_k(i). \]

(Go back the other way?)

A.1-7

Evaluate the product \(\prod_{k = 1}^n 2 \cdot 4^k.\)

Sol’n

\[ \begin{align*} \lg\left(\prod_{k = 1}^n 2 \cdot 4^k\right) & = \sum_{k = 1}^n \lg\left(2 \cdot 4^k\right) \\ & = \sum_{k = 1}^n (2k + 1) \\ & = n(n + 2). \end{align*} \]

Thus \(\prod_{k = 1}^n 2 \cdot 4^k = 2^{n(n + 2)}.\)

A.1-8 ⭑

Evaluate the product \(\prod_{k = 2}^n \left(1 - 1/k^2\right).\)

Sol’n

\[ \begin{align*} \lg\left(\prod_{k = 2}^n \left(1 - 1/k^2\right)\right) & = \sum_{k = 2}^n \lg\left(1 - 1/k^2\right) \\ & = \sum_{k = 2}^n \lg\left(1 - 1/k^2\right) \\ \end{align*} \]

\(\dots\) TODO