Like Eureka!, only cooler

Concrete Mathematics Chapter 2 Basics

This second batch of exercises builds on the previous one. Once again, there are no complex manipulations, and very often the solution just follows from the definitions.


$\sum_{0\le k\lt n}(a_{k+1}-a_k)b_k$

To show that

\begin{align} \sum_{0\le k\lt n}(a_{k+1}-a_k)b_k & = a_n b_n - a_0 b_0 - \sum_{0 \le k \lt n} a_{k+1}(b_{k+1} - b_k)&&n\ge 0\\ \end{align}

I start by rewriting the sum in the right side of the equation:

\begin{align} \sum_{0 \le k \lt n} a_{k+1}(b_{k+1} - b_k) & = \sum_{0 \le k \lt n} (a_{k+1}b_{k+1} + a_{k+1} b_k)\\ & = \sum_{0 \le k \lt n} a_{k+1}b_{k+1} + \sum_{0 \le k \lt n} a_{k+1} b_k&&\text{associative law}\\ & = \sum_{0 \le k-1 \lt n} a_k b_k + \sum_{0 \le k \lt n} a_{k+1} b_k&&k\leftarrow k-1\\ & = \sum_{1 \le k \le n} a_k b_k + \sum_{0 \le k \lt n} a_{k+1} b_k\\ \end{align}

This latest value can now be put back into the original right:

\begin{align} a_n b_n - a_0 b_0 - \sum_{1 \le k \le n} a_k b_k + \sum_{0 \le k \lt n} a_{k+1} b_k & = \sum_{0\le k \lt n} a_{k+1} b_k - (a_0 b_0 + \sum_{1 \le k \le n} a_k b_k - a_n b_n)\\ & = \sum_{0\le k \lt n} a_{k+1} b_k - \sum_{0\le k \lt n} a_k b_k\\ & = \sum_{0\le k \lt n} (a_{k+1} b_k - a_k b_k)\\ & = \sum_{0\le k \lt n} (a_{k+1} - a_k) b_k\\ \end{align}

which is indeed the left side of the equation (the but-last step is permitted under the associative law, but that didn’t fit in the margin).

$p(k) = k + (-1)^k c$

It is clear that there is a single $p(k)$ for every possible (integer) $k$. So I need to show that for every $m$, there is a single $k$ such that $p(k)=m$, defining $p^{-1}$.

The book method is smart, mine clearly less so, but as far as I can tell, still correct: for $m$, I consider $m-c$ and $m+c$. The difference is $2c$, so they’re either both even, or both odd.

If they’re both even, then $m-c+(-1)^{m-c}c=m$, so $k=m-c$. If they’re both odd, then $m+c+(-1)^{m+c}c=m$, so $k=m+c$. So $k$ is always well defined for every $m$, and $p$ is indeed a permutation.

$\sum_{k=0}^n (-1)^k k^2$

While I found the closed formula for the sum, I could not do it with the repertoire method.

Solving the sum is not really difficult (although a little bit more than the repertoire method, if you know how to do the latter); one way is to solve the positive and negative sums separately (they can be broken down to already solved sums); another one is to compute the sum of an even number of terms (one positive and one negative), then to compute sums of odd number of terms (by adding a term to the previous solution), and finally combining both to find the closed formula.

In both attempts above, I tried to remove the $(-1)^k$ factor from the terms; when using the repertoire method I tried to do the same, which is why I failed.

The repertoire method relies on a good intuition: one must have a sense of general shape of the parametric functions. In retrospect, it seems obvious, but I just couldn’t see it, blinded as I was by$(-1)^k$.

Expressing the sum as a recurrence is easy:

\begin{align} R_0 & = 0\\ R_n & = R_{n-1} + (-1)^n n^2\\ \end{align}

Also, looking at the first few terms of the sum, $-1, 3, -6, 10, -15, \dots$, it is natural to consider solutions of the form $(-1)^n F(n)$; it is a little bit trickier to see where a good generalisation of the recurrence above should put the additional terms:

\begin{align} R_0 & = \alpha\\ R_n & = R_{n-1} + (-1)^n \left(\beta + \gamma n + \delta n^2 \right)\\ \end{align}

With such a form, plugging in solutions $(-1)^nF(n)$ will simplify to $F(n) = \beta + \gamma n + \delta n^2 - F(n-1)$.

At this stage, it becomes very easy to find the $A(n)$, $B(n)$, $C(n)$ and $D(n)$ functions (the latter being the solution we are looking for). In fact, if all you care about is $D(n)$, then it is enough to use $R_n = (-1)^n n$ and $R_n = (-1)^n n^2$:

$R_n = (-1)^n n$

\begin{align} R_0 & = 0&&\alpha = 0\\ n & = \beta + \gamma n + \delta n^2 - n + 1\\ 2n - 1 & = \beta + \gamma n&&\beta = -1, \gamma = 2\\ \end{align}

which gives $-B(n)+2C(n) = (-1)^n n$.

$R_n = (-1)^n n^2$

\begin{align} R_0 & = 0&&\alpha = 0\\ n^2 & = \beta + \gamma n + \delta n^2 - (n-1) ^2\\ 2 n^2 - 2n + 1 & = \beta + \gamma n + \delta n^2&&\beta = 1, \gamma = -2, \delta = 2\\ \end{align}

which gives $B(n)-2C(n)+2D(n) = (-1)^n n^2$. Combining with the previous answer, we have $2D(n) = (-1)^n (n^2-n)$, or $D(n) = (-1)^n \frac{n^2-n}{2}$.

Wrapping up this exercise

In hindsight, these steps could have helped me solve this exercise as intended:

  • compute the first few terms to see if there is something obvious about their shape; in this case, the $(-1)^n$ factor
  • at first, write the recurrence equations as simply as possible, with all the “inconvenient” parts; comparing them to the “shapes” identified in the previous step might give some insight about the general solutions, and possibly removed these difficult parts
  • only then, consider how to generalise the recurrence equations. The base case is always $R_0 = \alpha$; the recurrent case should add parameters to each term, and additional terms (with their own parameters) to complete some basic classes of problems (for instance, if there are any polynomial, there should be a term for each power smaller than the largest power of the original problem; another basic class is the generalised radix-based Josephus problem)
  • each class of problems can be solved independently; this makes it easier to find potential solutions and to combine them.

$\sum_{k=1}^n k2^k$

Not overly complicated; at least the introduction of $j$ is not a mystery (unlike the next exercise).

\begin{align} \sum_{1\le k\le n}k 2^k & = \sum_{1\le k\le n} 2^k \sum_{1\le j\le k}1\\ & = \sum_{1\le k\le n} \sum_{1\le j\le k} 2^k\\ & = \sum_{1\le j\le k \le n} 2^k\\ & = \sum_{1\le j\le n} \sum_{j\le k\le n}2^k\\ \end{align}

The inner sum can be rewritten as

\begin{align} \sum_{j\le k\le n}2^k & = \sum_{1\le k\le n}2^k - \sum_{1\le k\lt j}2^k\\ & = 2^{n+1} - 2 - 2^j + 2\\ & = 2^{n+1} - 2^j\\ \end{align}

Here I use the already known sum $\sum 2^k$. Putting this last result in the original sum

\begin{align} \sum_{1\le j\le n} 2^{n+1} - 2^j & = n2^{n+1} - (2^{n+1} -2)\\ \end{align}

$\sum_{k=1}^n k^3$

It took me some time to convince myself that the original rewrite was legitimate; eventually I did it by induction (the book version is much shorter, and once you see it, much easier). Clearly it works for $n=1$, so assuming it does for $n-1$, we have

\begin{align} 2\sum_{1\le j\le k\le n} jk & = 2\sum_{1\le j\le k\le n-1} jk + 2\sum_{1\le j\le k=n} jk\\ & = \sum_{1\le k\lt n}(k^3+k^2) + 2n\sum_{1\le j\le n} j\\ & = \sum_{1\le k\lt n}(k^3+k^2) + n^2(n+1)\\ & = \sum_{1\le k\lt n}(k^3+k^2) + n^3+n^2\\ \end{align}

So the rewrite is correct. At this stage, (2.33) pretty much finishes it:

\begin{align} \sum_{1\le k\le n}(k^3+k^2) & = (\sum_{1\le k\le n}k)+\sum_{1\le k\le n}k^2\\ \end{align}

so $\sum_{1\le k\le n}k^3=\frac{n^2(n+1)^2}{4}$.

$\frac{x^{\underline m}}{(x-n)^{\underline m}} = \frac{x^{\underline n}}{(x-m)^{\underline n}}$

This follows directly from $\frac{a}{b} = \frac{c}{d} \implies ad = bc$, and the use of equation (2.52).

Rising and Falling Factorial Powers Conversions

I’ll just do the conversion from raising factorial power to falling factorial power; the other conversion is just the same.

$x^{\overline m} = \frac{1}{(x-1)^{\underline m}}$ follows from (2.51) and (2.52).

For the other equalities, by induction on $m$, and using (2.52) and its raising factorial powers equivalent:

\begin{align} x^{\underline m} & = x^{\underline{m-1}}(x-m+1)\\ & = x^{\underline 1}(x-1)^{\underline{m-1}}\\ & = x(x-1)^{\underline{m-1}}\\ x^{\overline m} & = x^{\overline{m-1}}(x+m-1)\\ & = x^{\overline 1}(x+1)^{\overline{m-1}}\\ & = x(x+1)^{\overline{m-1}}\\ \end{align}

Base case $m=0$

They all follow from definition:

\begin{align} x^{\overline 0} & = 1\\ (-1)^0 (-x)^{\underline 0} & = 1\\ (x+0-1)^{\underline 0} & = 1\\ \end{align}

Other positive $m$

Assuming the relations hold for all $k, 0\le k\lt m$:

\begin{align} (-1)^m(-x)^{\underline m} & = -\left((-1)^{m-1}(-x)^{\underline{m-1}}(-x-m+1)\right)\\ & = (x^{\overline{m-1}})(x+m-1)\\ (x+m-1)^{\underline m} & = (x+m-1)^{\underline{m-1}}x\\ & = (x+1+(m-1)-1)^{\underline{m-1}}x\\ & = (x+1)^{\overline{m-1}}x\\ \end{align}

Negative $m$

Using the recurrence relations derived from (2.52) and its raising factorial power equivalent:

\begin{align} x^{\underline m} & = x^{\underline{(m+1)+(-1)}}\\ & = x^{\underline{-1}}(x+1)^{\underline{m+1}}\\ & = \frac{(x+1)^{\underline{m+1}}}{x+1}\\ & = x^{\underline{m+1}}(x-m-1)^{\underline{-1}}\\ & = \frac{x^{\underline{m+1}}}{x-m}\\ x^{\overline m} & = x^{\overline{(m+1)+(-1)}}\\ & = x^{\overline{-1}}(x-1)^{\overline{m+1}}\\ & = \frac{(x-1)^{\overline{m+1}}}{x-1}\\ & = x^{\overline{m+1}}(x+m+1)^{\overline{-1}}\\ & = \frac{x^{\overline{m+1}}}{x+m}\\ \end{align}

Assuming the relations hold for all $k, m\lt k\le 0$:

\begin{align} (-1)^m(-x)^{\underline m} & = -\frac{(-1)^{m+1}(-x)^{\underline{m+1}}}{-x-m}\\ & = \frac{x^{\overline{m+1}}}{x+m}\\ (x+m-1)^{\underline m} & = \frac{(x+m)^{\underline{m+1}}}{x+m-1-m}\\ & = \frac{(x-1)^{\overline{m+1}}}{x-1}\\ \end{align}

So the main difficulties is to derive two equalities from (2.52) (four if we count the negative cases as well), and the identification of the recurrence equation in the induction step (especially for $(x+m-1)^{\underline{m\pm 1}}$).

Absolute Convergence of Complex Sums

I suppose I could say it follows directly from the equivalence of the metric functions (if my memory of metric space terminology is correct).

More basically, the equivalence of the propositions follows from the relationships based on the hypotenuse formula: $\sqrt{(Rz)^2+(Iz)^2}\le |Rz| + |Iz|$, so the absolute convergence of the real and imaginary parts implies the absolute convergence of the absolute value. Conversely, $|Rz|,|Iz|\le\sqrt{(Rz)^2+(Iz)^2}$, so the absolute convergence of the absolute value also implies the absolute convergence of both the real and imaginary parts.

Wrapping up

This time, I found a solution to all the exercises, which is a progress of some sort. I still have trouble with the repertoire method, or perhaps not with the method itself but in identifying suitable generalisations and candidate solutions. This is something that can only be developed with practice, so I just have to be patient and keep trying (I hope I’ll get there eventually).