Pensieve header: Solving Quiz 1 on the computer.

sl[1] = {"","1"}; (* "sl" for "subsets list" *)
sl[n_] := sl[n] = Join[
sl[n-1],
(#<>ToString[n])& /@ Reverse[sl[n-1]]
]

sl[1] /. "" -> "∅"

sl[2] /. "" -> "∅"

sl[3] /. "" -> "∅"

sl[4] /. "" -> "∅"

sl[5] /. "" -> "∅"

bp[n_,0] = bp[n_,n_] = 1; (* "bp" for "binary pascal" *)
bp[n_,k_] := bp[n,k] = (bp[n-1,k-1]+bp[n-1,k]) /. 2->0

Sum[bp[1000,k], {k,0,1000}]

ArrayPlot[
Table[bp[n,k], {n,0,200}, {k,0,n}]
]

S[0]=1;
S[n_] := 2*S[n-(2^(Floor[Log[2,n]]))];
S[1000]