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