This seems like a fairly easy induction problem but I am a bit rusty. I have the first two steps -- that the statement holds for $n = 1$, and I am assuming that for $n = k$, $k(k - 1) < 2^k$.
Now for showing it holds for $n = k + 1$:
$(k + 1)(k + 1 - 1) < 2^{k + 1}$
$k(k + 1) < 2^{k + 1}$
$k^2 + k < 2^{k + 1}$
... here I am stuck. Can anyone point me in the right direction?