Lines in the Plane

This chapter of Concrete Mathematics reads nicely, without issues so far. I pause often, either to think over the text, draw an image, or write down a table/derivation. My imagination finds fiddling with pen and paper helpful.

The authors of the book introduce the term I wasn't aware of: triangular numbers. Each such Nth number equals the sum of natural numbers from 1 to N. The following table shows the first seven triangular numbers.

N	1	2	3	4	5	6	7
sum	1	3	6	10	15	21	28

Also, we are elegantly introduced to Gauss's formula for summing up the first N natural numbers.

Reading the chapter, I've got a metaphor born:

Mathematics can be looked at as a large programming language, to the standard library of which new methods/functions (closed-form formulas) are added by the mathematicians of the world.

Speaking of closed forms, let's prove — using the method of mathematical induction — that, for the recurrence relation

$\begin{equation*} \flushleft L_0 = 1 \ ; \\ L_n = L_{n-1} + n \ , \qquad \text{for } n > 0 \ , \end{equation*}$ 1

the closed-form expression is

$\begin{equation*} L_n = \frac{n(n + 1)}{2} + 1 \ , \qquad \text{for } n \ge 0 \ . \end{equation*}$ 2

Proof

Base case. For $n = 0$ ,

$\begin{align*} L_0 &= \frac{0 * (0 + 1)}{2} + 1 \qquad \textit{\small by substitution from (2)} \\ &= \frac{0}{2} + 1 \\ &= 0 + 1 \\ &= 1 \ . \end{align*}$

But $L_0 = 1$ by (1) also, hence (2) is true for the base case.

Inductive step. For an arbitrary positive number $k$ , such that $n = k$ , suppose that

$\begin{equation*} L_k = \frac{k(k + 1)}{2} + 1 \ . \end{equation*}$ 3

Now we must show that for $n = k + 1$ :

$\begin{align*} L_{k+1} &= \frac{(k + 1)(k + 1 + 1)}{2} + 1 \\ &= \frac{(k + 1)(k + 2)}{2} + 1 \ . \end{align*}$ 4

Observe that

$\begin{align*} L_{k+1} &= L_{(k+1)-1} + (k + 1) \qquad \textit{\small by (1)} \\ &= L_k + k + 1 \\ &= \frac{k(k + 1)}{2} + 1 + k + 1 \qquad \textit{\small by (3)} \\ &= \frac{k(k + 1)}{2} + 1 + \frac{2(k+1)}{2} \\ &= \frac{k(k + 1)}{2} + \frac{2(k+1)}{2} + 1 \\ &= \frac{k(k + 1) + 2(k + 1)}{2} + 1 \\ &= \frac{(k + 1)(k + 2)}{2} + 1 \ , \end{align*}$

as was to be shown.

Hence this establishes (2).

And we proceed to the next chapter.