递推公式
[F(n)=egin{cases}
0&(n=0)& \
1&(n=1)& \
2F(n-1)+1 &(n>1)&
end{cases}
]
构造生成函数求解
[egin{array}{lcl}
G(x)=1 cdot x^1+3cdot x^2+7cdot x^3+15cdot x^4 +cdots\\
2xcdot G(x)=qquad 2cdot x^2+6cdot x^3 +14 cdot x^4;+cdots\\
G(x)-2xcdot G(x)=x^1+x^2+x^3+x^4+cdots\\
(1-2x)G(x)=frac{1}{1-x}-1 \\
(1-2x)G(x)=frac{x}{1-x} \\
G(x)=frac{x}{(1-2x)(1-x)}=frac{1}{1-2x}-frac{1}{1-x}\\\
qquad;;=(1+2x+2^2x^2+2^3x^3+cdots+2^nx^n)-(1+x^1+x^2+cdots+x^n)\\
qquad;;=(2^1-1)x+(2^2-1)x^2+cdots(2^n-1)x^n\\
Rightarrow F(n)=2^n-1
end{array}
]