# Thread: Prove by induction that for every positive integer n

1. ## Prove by induction that for every positive integer n

Sum $\sum_{i=1}^{n} 2^{i} = 2^{n+1} -2$

Could Anyone please give me an Idea of how I would go about solving this problem .?

Any advice would be appreciated cheers.

2. ## Re: Prove by induction that for every positive integer n

The problem says "by induction". Can we assume you know what that means?

First, of course, when n= 1, $\displaystyle \sum_{i=1}^n 2^i= 2^1= 2$ while $\displaystyle 2^{n+1}- 2$ is $\displaystyle 2^2- 2= 4- 2= 2$. So the statement is true when n= 1.

Now suppose the statement is true for n= k, say. That is, suppose $\displaystyle \sum_{i=1}^k= 2^{k+1}- 2$. Then $\displaystyle \sum_{i=1}^{k+1} 2^i$ is just the same sum with one additional term: $\displaystyle \sum_{i=1}^{k+1} 2^i= \left(\sum_{i= 1}^k 2^i\right)+ 2^{k+1}$. Replace that $\displaystyle \sum_{i=1}^k 2^i$ with $\displaystyle 2^k- 2$ and do the algebra.

3. ## Re: Prove by induction that for every positive integer n

Thanks HallsofIvy,
Induction means a mathematical technique which is used to prove a statement, a formula or a theorem is true for every natural number.
Do I simply just sub in 1 for k into 2^k -2 which you have written after the last summation?
making it equal to 2 -2 = 0? and compare it with the earlier summation
I'm kinda not sure how to do the second part with the k+1 power added and break it down from there ....

Sum $\sum_{i=1}^{k+1} 2^{i}$ =( Sum $\sum_{i=1}^{k+1} 2^{i}$)+2^k+1 replacing that Sum $\sum_{i=1}^{k} 2^{i}$ with 2^k - 2

how you broke it down I'm a little confused with ....
Thanks

4. ## Re: Prove by induction that for every positive integer n

Thanks HallsofIvy,
Induction means a mathematical technique which is used to prove a statement, a formula or a theorem is true for every natural number.
Do I simply just sub in 1 for k into 2^k -2 which you have written after the last summation?
making it equal to 2 -2 = 0? and compare it with the earlier summation
I'm kinda not sure how to do the second part with the k+1 power added and break it down from there ....

Sum $\sum_{i=1}^{k+1} 2^{i}$ =( Sum $\sum_{i=1}^{k+1} 2^{i}$)+2^k+1 replacing that Sum $\sum_{i=1}^{k} 2^{i}$ with 2^k - 2

how you broke it down I'm a little confused with ....
Thanks

6. ## Re: Prove by induction that for every positive integer n

Originally Posted by bee77
Sum $\sum_{i=1}^{n} 2^{i} = 2^{n+1} -2$

Could Anyone please give me an Idea of how I would go about solving this problem .?

Any advice would be appreciated cheers.
Let's approach this three ways. We want to prove that P(n) is true for every natural number.

The formal approach. Let S be the set for which every element s is a natural number such that P(s) is true. But S may be empty. So prove P(1) is true. Thus S is not empty. Let k be ANY element of S (there is at least one element in S). Because k in S, P(k) is true. So we we know that 1, k, and k + 1 are all natural numbers and that P(1) and P(k) are true. Using those five facts prove P(k+1) is true. Thus k + 1 in S. Therefore S = N.

That is the formal structure of a proof by weak mathematical induction.

The intuitive approach. If something is true for 1 and for the next number past a number for which that something is true, then it is true for 1, but it is also true for 1 + 1, the number next after 1 or 2, which makes it true for the number next after 2, or 3, which makes it true for 4 and then 5 and so on forever. The intuition is of an infinite number of dominoes falling.

The practical approach. The n = 1 step is usually easy. The challenge arises on the k to k + 1 step. There probably is no general way to attack all proofs by induction, but a very common practical approach when you are asked to equate two expressions is to form your expression in k + 1 and expand it into an expression involving k and known numbers without any mention of (k + 1).

$\displaystyle \text {PROVE: } n \in \mathbb N^+ \implies \sum_{j=1}^{n} 2^{j} = 2^{(n+1)} - 2.$

First, prove for n = 1.

$\displaystyle n = 1 \implies \sum_{j=1}^{n} 2^{j} = \sum_{j=1}^{1} 2^{j} =$

$2^1 = 2 = 4 - 2 = 2^2 - 2 = 2^{(1+1)} - 2 = 2^{(n+1)} - 2.$

That was easy enough.

Second step.

$\displaystyle \text {LET: } k \text { be any number such that } k \in \mathbb N^+ \text { and } \sum_{j=1}^{k} 2^{j} = 2^{(k+1)} - 2.$

We can say that because we know that there is at least one such number, namely 1, but we are not assuming that k = 1.

OK before we actually try to do the proof, let's be sure to grasp what are we trying to do. We want to prove that

$\displaystyle \sum_{j=1}^{k+1} 2^{j} = 2^{\{(k+1)+1\}} - 2.$

Let's expand the first expression into something that does not involve (k + 1) at all.

$\displaystyle \sum_{j=1}^{k+1} 2^{j} = \left ( \sum_{j=1}^k 2^{j} \right ) + 2^{(k+1)} = \left ( \sum_{j=1}^k 2^{j} \right ) + (2 * 2^k).$

That was not so hard, was it?

$\text {BUT} \displaystyle \sum_{j=1}^{k} 2^{j} = 2^{(k+1)} - 2 = (2 * 2^k) - 2.$

$\therefore \displaystyle \sum_{j=1}^{k+1} 2^{j} = \left ( \sum_{j=1}^k 2^{j} \right ) + (2 * 2^k) =$

$(2 * 2^k) - 2 + (2 * 2^k) = (4 * 2^k) - 2 = (2^2 * 2^k) - 2 = 2^{(k+2)} - 2 = 2^{\{(k+1)+1\}} - 2.$

Done.

7. ## Re: Prove by induction that for every positive integer n

Ok Thanks HallsofIvy .

Thanks Jeff.