S_k = 2^k