Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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
up vote 0 down vote accepted

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$.

share|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.