在状压 DP 中枚举子集有这样的代码：

    for (int i = 0; i < (1 << n); ++i) {
        for (int j = i; j; j = (j - 1) & i) 
            //do something...
    }

很想质疑这个玩意复杂度为 $O(n^3)$，于是开推式子

最终（稍微修改与变形）得到这个玩意

$\sum^n_{i=0} 2^i {{n}\choose{i}}$

打表看了一下就是 $3^n$。

求问大佬们怎么证明》》》？？？