Exploration of sums

Table of Contents

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:

consecutive-pos-ints.png

Reflect the blue dots through an imaginary line of symmetry, and we use a different color to highlight the reflected dots:

consecutive-pos-ints-filled.png

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*}

Author: Max Beutel

Created: 2020-05-17 Sun 09:50

Validate