# Thread: using mathematical induction to prove something

1. ## using mathematical induction to prove something

Hey guys having some trouble with this question I just don't really know where to go with it..

Use mathematical induction to prove that, for all integers n ≥ 1

n
2^(j-1) = (2^n)-1.
j=1

2. $\displaystyle P(n) : \sum_{j = 1}^{n} 2^{j-1} = 2^{n} - 1$

Prove that P(1) is true:
$\displaystyle \sum_{j = 1}^{1} 2^{0} = 1$
$\displaystyle 2^{1} - 1 = 1$

Now assume P(k) is true. We must show that this implies
$\displaystyle P(k+1): \sum_{j = 1}^{k+1} 2^{j-1} = 2^{k+1} - 1$

So, we have that:
$\displaystyle P(k+1): \sum_{j = 1}^{{\color{red}k+1}}2^{j-1} = \underbrace{\sum_{j=1}^{k}2^{j-1}}_{P(k)} + {\color{red} \: 2^{(k+1)-1}} = \underbrace{\left(2^{k} - 1\right)}_{P(k)} + 2^{k}$

Can you go on from that?

3. Originally Posted by o_O
$\displaystyle P(n) : \sum_{j = 1}^{n} 2^{j-1} = 2^{n} - 1$

Prove that P(1) is true:
$\displaystyle \sum_{j = 1}^{1} 2^{0} = 1$
$\displaystyle 2^{1} - 1 = 1$

Now assume P(k) is true. We must show that this implies
$\displaystyle P(k+1): \sum_{j = 1}^{k+1} 2^{j-1} = 2^{k+1} - 1$

So, we have that:
$\displaystyle P(k+1): \sum_{j = 1}^{{\color{red}k+1}}2^{j-1} = \underbrace{\sum_{j=1}^{k}2^{j-1}}_{P(k)} + {\color{red} \: 2^{(k+1)-1}} = \underbrace{\left(2^{k} - 1\right)}_{P(k)} + 2^{k}$

Can you go on from that?
Hey thanks heaps for the reply!! Just wondering where the (-1) in {\color{red} \: 2^{(k+1)-1}} comes from?

Thanks again.

4. Because of $\displaystyle \sum\limits_{j\,=\,1}^{k+1}{2^{j-1}}=\sum\limits_{j\,=\,1}^{k}{2^{j-1}}+\sum\limits_{j\,=\,k+1}^{k+1}{2^{j-1}}.$