S_{k+1} = \sum_{s=0}^{k+1}{ {k+1} \choose {s}}= {{k+1} \choose {0}}+ \sum_{s=1}^{k}{ {k+1} \choose {s}} + {{k+1} \choose {k+1}}