# using mathematical induction to prove something

• Apr 29th 2008, 08:11 PM
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
http://sigma.ontologyportal.org:4010...igmaSymbol.gif 2^(j-1) = (2^n)-1.
j=1

• Apr 29th 2008, 08:22 PM
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?
• Apr 30th 2008, 07:18 PM
Quote:

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.
• Apr 30th 2008, 07:32 PM
Krizalid
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}}.$