# triangular number theorem

$$n:\mathbb{N} \mid n>0 \vdash 2^{n-1}(2^n-1) = 1 + 2 + 3 + \ldots + (2^n-1)$$

## proof: by induction

### Base case

prove for $n = 1$:

$$2^{1-1}(2^1-1) = 1(2-1) = 1 = 2^1 -1 \\ \square$$

### Inductive step

assume true for $n = k$; prove for $n = k+1$:

$$1 + 2 + 3 + \ldots + (2^{k+1}-1) \\ = 1 + 2 + 3 + \ldots + (2^k-1) + 2^k + (2^k+1) + (2^k+2) + \ldots + (2^{k+1}-1) \\ = 1 + 2 + 3 + \ldots + (2^k-1) + 2^k\times 2^k +1 + 2 + \ldots + (2^{k}-1) \\ = 2(1 + 2 + 3 + \ldots + (2^k-1)) + 2^k\times 2^k \\ = 2(2^{k-1}(2^k-1)) + 2^k\times 2^k \\ = 2^{k}(2^k-1 + 2^k) \\ = 2^{k}(2^{k+1}-1) \\ \square$$
$\square$