Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
Do you know what is a proof by induction? –  Martín-Blas Pérez Pinilla Feb 6 at 10:25
    
I really know it, that's why I'm asking –  Rafael Feb 6 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 at 10:44

2 Answers 2

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|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 Feb 6 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|improve this answer

Your Answer

 
discard

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.