# Exploration of sums

## 1 Exploration of sums

### 1.1 Sum from $$1$$ to $$n$$

We want to find:

\begin{equation*} S = 1 + 2 + 3 + ... + n \end{equation*}

Let's create a visualization for the first $$4$$ positive integers: Reflect the blue dots through an imaginary line of symmetry, and we use a different color to highlight the reflected dots: In the general case, for the first $$n$$ positive integers, we get a rectangle of dots having $$w$$ dots along the horizontal side and $$h$$ dots along the vertical side. In total we will have $$w \times h$$ dots forming the rectangle consisting of blue and green dots.

But we only want to find the sum of the blue dots, as these represent the first $$n$$ positive integers. Call this sum $$S$$, and we can find it by only counting half of the dots in the rectangle: $$S = \frac{1}{2}(w \times h)$$. But $$w = n$$ (as we lined up $$n$$ integers) and $$h = n+1$$ (because of the reflection), so we rewrite $$S = \frac{n(n+1)}{2}$$.

It is interesting to understand why $$h=n+1$$. Note that when reflecting the blue dots, we also created a row of only green dots. Thus we don't have a square of $$n \times n$$ dots but instead a rectangle of the dimensions $$n \times (n+1)$$.

### 1.2 Sum of an arithmetic sequence (of $$n$$ terms)

Let $$x_1=a$$ be the first term in the sequence, $$x_n = x_{n-1} + d$$ any subsequent term for $$n=2,3,...$$ and $$d$$ be the difference we add to reach the next term in the arithmetic sequence.

Find some terms:

\begin{align*} x_1 &= a \\ x_2 &= a + d \\ ... \\ x_n &= a + \smash{\underbrace{d + ... + d}_{(n-1)\text{ times}}} \end{align*}

Now we want to find $$S$$, the sum of these $$n$$ terms:

\begin{align*} S &= x_1 + x_2 + ... + x_n \\ &= a + (a + d) + ... + (a + d + ... + d) \end{align*}

Since we have $$n$$ terms and each term has an $$a$$, we can simplify the formula for $$S$$ somewhat by extracting $$a$$ such as:

\begin{align*} S &= \color{red}{n \times a} + (d) + ... (d + ... + d) \end{align*}

Let's add up the remaining $$d$$'s we have. To do that, first count how many $$d$$'s there are in $$S$$. $$x_1$$ has $$0$$ $$d$$'s in it, $$x_2$$ has $$1$$ $$d$$ in it, all the way up to $$x_n$$ which has $$(n-1)$$ $$d$$'s in it. So, if we just want to sum up the number of $$d$$'s, we can do that using a standard formula:

\begin{equation*} \text{number of d's} = 1 + 2 + ... + (n-1) = \frac{(n-1)n}{2} \end{equation*}

and now we rewrite the formula for $$S$$ once again:

\begin{align*} S &= n \times a + \color{red}{ d \times \frac{(n-1)n}{2} } \\ &= n \times a + d \times \frac{n^2 - n}{2} \end{align*}

### 1.3 Sum of a geometric sequence (of $$n$$ terms)

Let $$u_1=a$$ be the first term in the sequence, $$u_n = u_{n-1} r$$ any subsequent term for $$n=2,3,...$$ and $$r$$ be the ratio to find the next term in the sequence.

To get some inspiration how we would find a closed form for $$S = a + ar^1 + ... + ar^{n-1}$$, let's explore an example:

\begin{align} 10000 - 1 &= 9999 = 9(1111) \\ \frac{10000 - 1}{9} &= 1111 \\ \frac{10^4-1}{10-1} &= 10^0 + 10^1 + 10^2 + 10^3 \end{align}

How was that useful? In equation (3), we found a closed form for a summation of in total $$\color{red}{4}$$ terms, each a power of $$10$$. Define $$r=10$$ and rewrite (3) like so:

\begin{equation*} \frac{r^{\color{red}{4}} - 1}{r-1} = r^0 + r^1 + r^2 + r^3 \end{equation*}

That looks a lot like the part of $$S = a + ar^1 + ... + ar^{n-1} = a\color{red}{r^0} + a\color{red}{r^1} + ... + a\color{red}{r^{n-1}}$$ where the powers are involved (note that $$r^0=1$$.) Let's use this knowledge and try to find a closed form for the sum:

\begin{align*} S &= a + ar^1 + ... + ar^{n-1} \\ &= a (r^0 + r^1 + ... + r^{n-1}) \\ &= a \left( \frac{r^n - 1}{r-1} \right) \end{align*}

### 1.4 Deriving the formula for a first-order linear recurrence system

Define the following first-order linear recurrence system:

\begin{align*} u_1 &= a \\ u_n &= ru_{n-1} + d \\ n &= 2,3,... \end{align*}

Let's find some terms:

\begin{align*} u_1 &= a \\ u_2 &= ru_1 + d = ra + d \\ u_3 &= ru_2 + d = r(ra + d) + d = r^2a + rd + d \\ ... \\ u_n &= ru_{n-1} + d = r^{n-1}a + r^{n-2}d + ... + r^0d \end{align*}

We use $$r^0=1$$ in the last line to make it easier to use a formula for summing up the powers of $$r$$. Do it like this:

\begin{align*} u_n &= r^{n-1}a + d(r^{n-2} + ... + r^0) \\ &= r^{n-1}a + d \left( \frac{r^{n-1} - 1}{r-1} \right) \end{align*}

Usually some more algebraic manipulations are done to end up with:

\begin{align*} u_n &= \left( a - \frac{d}{1-r} \right) r^{n-1} + \frac{d}{1-r} \end{align*}

Created: 2020-05-17 Sun 09:50

Validate