最終的にmod2で考えるから単純に最初の変形は
2^k=1+農{i=1}^{k}2^{i-1}　k=1、2、…、
でよかったな。
2行目は余分だった。
あと、2進表示に変えたときの漸化式は
f(k)=農{i=1}^{k}f(i-1)、k=1、2、…、　f(0)=1、f(1)=f(2)=2、
になる。f(k)、k=0、1、2、…、の意味は同じ。