1/2+(2+3/4)+(4+7/8)+(6+15/16)+...+(2n-2+(2^n-1)/2^n)
=1-1/2+3-1/4+5-1/8+7-1/16)+...+(2n-1)-1/2^n
=(1+3+5+7+...+2n-1)-(1/2+1/4+1/8+1/16+...+1/2^n)
=n^2-(1-1/2^n)
=n^2-1+1/2^n