solving a problem with induction
-
28-09-2020 - |
Question
The original question is the following
prove that $2·\sum_{i=0}^{n-1} 3^{i} = 3^n-1$ for all n $\geq$ 1
I know that I have to prove by induction and have successfully done the base case, my IH is the following:
Assume $2·\sum_{i=0}^{n-1} 3^{i} = 3^n-1$ holds for all n $\geq$ 1 to prove $2·\sum_{i=0}^{n} 3^{i} = 3^{n+1}-1$
then I did this: $2·\sum_{i=0}^{n} 3^{i} = 2·\sum_{i=0}^{n-1} 3^{i} +3^n$
then by my IH: $2·\sum_{i=0}^{n-1} 3^{i} +3^n = 3^n-1+3^n $
after this I struggle to continue, I know I have to find a way to rewrite it to $3^{n+1}-1$ and I know this is equal to $3·3^n-1$ but I don't see how to get from the one to the other. Anyone who can help?
edit: I mistook a 2 for a 3, can anyone help now?
Solution
You can add the first pair of paranthesis in the derivation below, so that it becomes clear that the factor $2$ also multiplies the second term, as follows:
$2 \cdot \sum_{i=0}^n 3^i = 2 \cdot \left(\sum_{i=0}^{n-1} 3^i + 3^n \right) = 2 \cdot \sum_{i=1}^{n-1} 3^i + 2 \cdot 3^n = (3^n -1 ) + 2 \cdot 3^n = 3^{n+1}-1.$
OTHER TIPS
$2·\sum_{i=0}^{n} 3^{i} = 3^n-1 +2\cdot{3^n}=3^{n+1}-1$.
Considering that the statement is incorrect (indeed $2\cdot\sum\limits_{i=0}^{n-1}2^i +1 =\sum\limits_{i=0}^{n}2^i = 2^{n+1}-1\neq 3^n$), I doupt anyone here can prove it.
As you can find as the basis of induction, it is not true even for $n = 2$ (Easy to see $2(1+2) = 6 \neq 3^2 - 1 = 8$).