The idea behind the sum of powers of 2 I know that the sum of power of $2$ is $2^{n+1}-1$, and I know the mathematical induction proof. But does anyone know how $2^{n+1}-1$ comes up in the first place.
For example, sum of n numbers is $\frac{n(n+1)}{2}$. The idea is that we replicate the set and put it in a rectangle, hence we can do the trick. What is the logic behind the sum of power of $2$ formula?

Not sure if my answer has been posted yet, but here's how I understand it.
You are trying to understand why 
$2^{n+1} - 1 = 2^n + 2^{n-1} + 2^{n-2} . . . + 2^1 + 2^0$
Suppose we take 2^n in the sum. We know since these are powers of two, that the previous term will be half of 2^n, and the term before that a quarter of 2^n. 
Let n in 2^n be 1, or 2^1 = 2. The term before in the sum will be half of 2, so we can also write the entire sum as: 
$2^1 + \frac{1}{2}(2^1)$ 
If you do this but for different values of n for 2^n you will find you can rewrite the sums as:
$2^n + \frac{ 2^n - 1}{2^n} ( 2^n)$
You can simplify this because you're dividing (2^n) - 1 by 2^n, and then multiplying it by 2^n which cancel each other out. The new simplified version with the cancellation will look like:
$2^n + 2^n - 1$
This can also be written as: $2( 2^n) - 1$
Further simplified into:  $2^{n + 1} - 1$
And that is why that formula shows up! Hope this helps ( I'm not sure if this was the mathematical induction proof you already knew, I'm young and discovered this on my own so I don't know what this is).
