I'm a little bit lost. I'm learning Math Discrete, and right now I'm in Proof by Induction. I have a question that uses a summation, and I never saw this kind of question before. Can someone help me? 🙁
Tese:
I dont know 🙁
$$2\sum_{j=1}^n \frac1{3^j} = 1- \left(\frac13\right)^n$$
$$2\cdot \frac13 + 2\cdot\frac{1}{3^2} + 2\cdot\frac1{3^3} + \dots + 2\cdot\frac{1}{3^n} = 1 – \left(\frac13\right)^n$$
Base ($n=1$):
\begin{align*}
2\cdot\frac1{3^1}&=1-\left(\frac13\right)^1\\
2\cdot\frac13 &= 1-\frac13\\
\frac23 &= 1-\frac13\\
\frac23 &= \frac23
\end{align*}
Best Answer
Congratulations on proving the initial $n=1$ case. The next step is to prove the induction step. That is, assuming the equality holds for $n$, prove that it holds for $n+1$. The reason this works is you have a base $n=1$ case you know to be true through other means, so if it's true for $n=1$ and you prove given $n=1$ that $(n=1)+1=2$ is true, you can reach $n=$ any number you like.
In general with induction with summations, try to remove the summation component(s). Those are the hardest to manipulate.
Given: $$2 \sum_{j=1}^{n} {1 \over 3^j} = 1-\left(1 \over 3 \right)^n$$ Check $$2 \sum_{j=1}^{n+1} {1 \over 3^j} = 1-\left(1 \over 3 \right)^{n+1}$$ Since you know that: $\sum_{i=1}^{m+1} f(i)= \sum_{i=1}^{m} f(i) + f(m+1)$, I would try that first. Also expand the right-hand side $$2 \sum_{j=1}^{n+1} {1 \over 3^j} = 2 \left(\sum_{j=1}^{n} {1 \over 3^j} + {1 \over 3^{n+1}}\right) = 2 \sum_{j=1}^{n} {1 \over 3^j} + {2 \over 3^{n+1}}$$ $$1-\left(1 \over 3 \right)^{n+1} = 1- \left({1 \over 3}\right)^n \times {1 \over 3}$$ Notice what you have now. The two halves of the equality that were given! $$\mathbf{2 \sum_{j=1}^{n} {1 \over 3^j}} + {2 \over 3^{n+1}} = \mathbf{1- \left({1 \over 3}\right)^n} \times {1 \over 3}$$ Substitute the left-hand side: $$1-\left(1 \over 3^n \right) + {2 \over 3^{n+1}} = 1- \left({1 \over 3^n}\right) \times {1 \over 3}$$ Let's put it over a common $3^{n+1}$ denominator: $$3^{n+1}-\left(3^{n+1} \over 3^n \right) + {2*3^{n+1} \over 3^{n+1}} = 3^{n+1}- \left({3^{n+1} \over 3^n}\right) \times {1 \over 3}$$ Simplify: $$3^{n+1}-3 + 2 = 3^{n+1}- 3 \times {1 \over 3}$$ Arithmetic: $$3^{n+1}-1 = 3^{n+1}-1$$ The above statement is true $\forall n$, so we have proven the induction step.