# $2^n-1 = \sum_{j<n}2^j$ induction explanation

I am having trouble understanding the following analysis after we arrived to the conclusion:

$2^k - \sum_{j=0}^{j=k-1}2^j = 1$

after arriving to the conclusion, they say, I think to explain that the left side is equal to 1:

"In fact, by induction on $n$ in $2^n-1 = \sum_{j<n}2^j$, in fact, $2^{n+1} - 1 = 2(2^n - 1) + 1 = 1 + \sum_{0<j<n+1}2^j = \sum_{j<n+1}2^j.$"

I am not even sure if the wrote the last part to prove $2^k - \sum_{j=0}^{j=k-1}2^j = 1$, is it to do that? If it is so, why?

Also, I do not see how we pass from $2(2^n - 1) + 1$ to $1 + \sum_{0<j<n+1}2^j$, and from $1 + \sum_{0<j<n+1}2^j$ to $\sum_{j<n+1}2^j$.

Thank you!

-
Do you know what is a proof by induction? – Martín-Blas Pérez Pinilla Feb 6 '14 at 10:25
I really know it, that's why I'm asking – Rafael Angarita Feb 6 '14 at 10:41
The trick: write $2^{n+1}−1$ in a way that allows using the induction hypothesis. – Martín-Blas Pérez Pinilla Feb 6 '14 at 10:44

Here's a less apocalyptic induction solution.

Let's note for all $n \in \mathbb{N}$, $P(n) : 2^n-1 = \sum_{j<n}2^j$.

$\sum_{j<0}2^j = 0 = 2^0-1$ so $P(0)$ is true.

Let's suppose that $\exists n \in \mathbb{N}$ such as $P(n)$ is true. So we have $2^n-1 = \sum_{j<n}2^j$.

$\sum_{j<n+1}2^j = 2^n+\sum_{j<n}2^j = 2^n +2^n-1$ according to the recurrence hypothesis.

So $\sum_{j<n+1}2^j = 2^{n+1}-1$ and consequently, $P(n+1)$ is true.

By recurrence over $\mathbb{N}$, $\forall n \in \mathbb{N}$, $P(n)$ is true.

Note : There is a much more straightforward proof : if we define $S_n$ to be $\sum_{j<n}2^j$, $2S_n = 2\sum_{j<n}2^j = \sum_{j<n}2^{j+1} = \sum_{j\in [1,n]}2^j = -1+2^{n}+\sum_{j<{n}}2^j = -1+2^{n}+S_n$.

So $S_n = 2^n-1$.

-
Thank you! It is really clear like that. Actually, the book I am reading is very apocalyptic, as you said. It has terrible explanations for almost everything, but it is an obligation to use it (some book from my faculty). – Rafael Angarita Feb 6 '14 at 10:47

Here is my solution by using induction explanation:

1. For $n=1$, we have $\displaystyle 2^{1}-1=1=\sum_{i=0}^{n-1}{2^{i}}$. So when $n=1$, the equation holds.
2. We suppose the equation holds when $n=k$, that is to say $\displaystyle 2^{k}-1=\sum_{i=0}^{k-1}{2^{i}}.$

For $n=k+1$, we have $\displaystyle 2^{k+1}-1=2^{k}+2^{k}-1=2^{k}+\sum_{i=0}^{k-1}{2^{i}}=\sum_{i=0}^{k}{2^{i}}.$

So we can get from 1. and 2. that the statement is true.

Actually, we needn't prove it in a induction explanation way, we can simply add all the number up in the right side by using subtract dislocation method and we can get the answer.

-