Identities to Know #

$$ \text{Let } S_{N} = 1 + 2 + … + (N-1) + N $$

Now add \(S_{N} \) with itself but reverse the order of the terms.

$$ \hspace{4pt} S_{N} = 1 + 2 + … + (N-1) + N $$

$$ + \frac{S_{N} = N + (N-1) + … + 2 + 1}{2S_{N} = (N+1) + (N+1) + … + (N+1)} $$

This gives us \(N\) number of \((N+1)\) terms. Dividing by two on both sides:

$$ 2S_{N} = N(N+1) \rightarrow S_{N} = \frac{N(N+1)}{2} $$

Let’s prove \( \sum_{i = 1}^{N}{i} = \frac{N(N+1)}{2} \) by induction.

First, let’s ensure the property holds for the base case \( N = 1 \):

$$ 1 \stackrel{?}{=} \frac{1(1 + 1)}{2} = \frac{2}{2} = 1 $$

Now, let’s assume that the property when \(N = k\) where \(k \) is some integer \( \geq 1 \). This our inductive hypothesis:

$$ \sum_{i = 1}^{k}{i} = \frac{k(k+1)}{2} $$

Now, let’s see if the property also holds for \(k+1\). From the property, we would expect to see that \( \sum_{i=1}^{k+1}{i} = \frac{(k+1)(k+2)}{2} \).

$$ 1 + 2 + 3 + … + k + (k+1) = \sum_{i = 1}^{k}{i} + (k+1) = \frac{k(k+1)}{2} + (k+1) $$

$$ = \frac{k^2 + k}{2} + \frac{2(k+1)}{2} = \frac{k^2 + 3k + 2}{2} = \frac{(k+1)(k+2)}{2} \quad \square $$

Which is the answer we would expect from the property.

To prove this property, I’m going to rewrite the sum slightly. Let \( n = \log_2{N} \), i.e. \( 2^n = N \).

$$ 1 + 2 + 4 + 8 + … + 2^n = 2N - 1 = 2(2^n) - 1 = 2^{n+1} - 1 $$

Let’s ensure that the property holds for the base case where \( n = 0 \):

$$ 1 \stackrel{?}{=} 2^{0 + 1} - 1 = 1 $$

Now, we make our inductive hypothesis. Let’s assume the property holds for \(n = k\) where \(k \) is an integer \( \geq 0\). We take the following to be true:

$$ 1 + 2 + 4 + … + 2^k = 2^{k+1} - 1 $$

Now, let’s see if, given that the inductive hypothesis is true, the property holds for \(n = k+1\). Based on the property, we would expect the sum up to \(2^{k+1}\) to equal \(2^{k+2} - 1 \).

$$ 1 + 2 + 4 + … + 2^k + 2^{k+1} = \left( 2^{k+1} - 1\right) + 2^{k+1} $$

$$ = 2 \left(2^{k+1} \right) - 1 = 2^{k+2} - 1 \quad \square $$