what's the best way to prove the equivalences of such formulas?

Question

I want to prove the following: $$2^n+2^{n-1}+...+2^1 + 1 = 2^{n+1}-1$$

The only Method that I know of is proof-by-induction but is this the best way to prove the equivalences of such formulas?

Answer 1

Multiply the left side by $(2-1)$, expand, and most of the terms cancel. What is left is your right side. That is the usual approach to finite geometric series.

Answer 2

Well, in this case you can recognize this as a geometric progression. Namely, if $$S = 1+a+a^2 + \cdots + a^n,$$then multiply it by $a$ to get $aS = a+a^2+a^3+\cdots + a^{n+1}$, and subtract both formulas to get $$aS-S = a^{n+1}-1,$$so that $$S = \frac{a^{n+1}-1}{a-1}.$$Now make $a=2$ and this becomes $$1+2+2^2+\cdots + 2^n = \frac{2^{n+1}-1}{2-1} = 2^{n+1}-1.$$

Answer 3

A direct proof is possible and very simple. Note that the left-hand side is a geometric series with ratio $2$ and first term $1$. Then

$$1+2 + 2^2 + \cdots + 2^n = \frac{2^{n+1} - 1}{2-1} = 2^{n+1} - 1$$

There's also a simple (arguably more intuitive) proof using binary notation for writing out your sum. The summation $1+2+\cdots +2^n$ is essentially $111\cdots 111$ in binary with $n+1$ ones. Add one and in the $(n+2)^{th}$ place (place value $2^{n+1}$), you would have a $1$ and zeroes elsewhere. This, you would have

$$(1+2+2^2+\cdots +2^n) + 1 = 2^{n+1}$$

with the desired result immediately following.

Answer 4

Our base case is $n=0$. In this case, $2^0=2^1-1=1$ so it is true.

Now, let us assume that the statement is true for $n=k$. We will prove it for $n=k+1$.

$2^{k+1}+2^{k}+2^{k-1}+2^{k-2}+\dots+2^3+2^2+2^1+2^0=2^{k+1}+(2^{k}+2^{k-1}+2^{k-2}+\dots+2^3+2^2+2^1+2^0)=2^{k+1}+2^{k+1}-1=2^{k+2}-1$.

Therefore, the statement is true for all nonnegative integers.

Answer 5

Let $S=1+2^1+2^2+\ldots \quad \ldots +2^{n-2}+2^{n-1}+2^{n}$. We have \begin{align} 2\cdot S=&0+2^1+2^2+\ldots \quad \ldots +2^{n-2} +2^{n-1}+2^{n}+2^{n+1} \end{align} Note that \begin{align} 2\cdot S-S=& 2^{n+1} +( 2^n-2^n)+( 2^{n-1}-2^{n-1})+\ldots \quad \ldots +(2^2-2^2)-(2^1-2^1)-1 \\ S=&2^{n+1}+\qquad 0\qquad +\qquad 0\qquad + \quad\ldots \quad\ldots+\qquad 0\qquad +\qquad 0\qquad -1 \\ S=& 2^{n+1}-1 \end{align}