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\)