Prove that $\sum\limits_{k=0}^n\ 2\times3^{k-1} = 3^n-1$

Question

Hope someone can enlighten me on how to show via induction that $\sum\limits_{k=0}^n\ 2\times3^{k-1} = 3^n-1$

I think you mean $$\sum^\boxed{n}_{\boxed{k}=\boxed{1}}2\times3^{k-1}=3^n-1$$ — , Apr 13 '14 at 21:01
There is a much nicer way than induction here. For sums of the form $\sum_k q^k$, multiply them by $(1-q)$ and see what you get. — mathse, Apr 13 '14 at 21:08
Another approach, if induction were not demanded, would be to do the arithmetic in base 3 notation. The equation to be proved says, in base 3, that $22\dots2+1=100\dots0$ (where the two $\dots$'s represent the same number of digits). This is just as obvious as the fact that, in base 10, $99\dots9+1=100\dots0$. — Andreas Blass, Apr 13 '14 at 22:23

score 1 · Accepted Answer · edited Apr 13 '14 at 21:07

1

$$\sum_{k = 0}^{n+1} 2 \times 3^{k-1} = \sum_{k = 0}^n 2 \times 3^{k-1} + 2 \times 3^n\\ = 3^n-1+ 2 \times 3^{n} = 3^{n+1}-1$$

edited Apr 13 '14 at 21:07

answered Apr 13 '14 at 21:03

Sandeep Silwal

8,135

This is obnoxious to read. Change your \times to \cdot and break it into multiple lines. – Cameron Williams Apr 13 '14 at 21:04
1

@user133281 This is the inductive step. – Ink Apr 13 '14 at 21:05

Wortic · Answer 2 · 2014-04-14T16:58:18.993

So, let's make this semi-rigorous. I assume that you already know the fundamental principles of mathematical induction so I won't go into great detail. Also, I assume that the sum starts at k=1, otherwise the statement isn't true ($\frac{2}{3}\neq0)$. We're going to divide this inductive proof into two steps

Step 1: Show that the statement is true when n=1

Step 2: Show that if the statement is true for the nth case it is also true for the n+1:th case

When those two steps are completed, we have shown that the statement is true for all k ($k\in\mathbb{N}$ and k>0)

Step 1: Well, this step is just as crucial as easy. Without it we won't tip any dominoes.$$\sum_{k=1}^{1}2\cdot3^{1-1}=2=3^1-1$$

Step 2: Now we replace n with n+1 and see what that will lead to $$\sum_{k=1}^{n+1}2\cdot3^{k-1}=\sum_{k=1}^{n}2\cdot3^{k-1}+2\cdot3^{n}$$if we use our induction assumption (that $\sum_{k=1}^{n}2\cdot3^{k-1}=3^n-1$) we get $$\sum_{k=1}^{n}2\cdot3^{k-1}+2\cdot3^{n}=3^n-1+2\cdot3^n=3\cdot3^n-1=3^{n+1}-1$$ We have shown that $$\sum_{k=1}^{n+1}2\cdot3^{k-1}=3^{n+1}-1$$ using the induction assumption. Thus we have shown that the nth case implies the n+1:th case and we have proven the statement using the principles of mathematical induction. Q.E.D.

score 0 · Answer 3 · answered Apr 13 '14 at 21:06

0

$$\sum_{k=1}^n 2\times3^{k-1} = \sum\limits_{k=1}^n (3-1)3^{k-1}= \sum\limits_{k=1}^n (3^k-3^{k-1}) = 3^n-1$$ by telescoping sum.

answered Apr 13 '14 at 21:06

Hans

9,804

Nice, but OP asks for induction. – vadim123 Apr 13 '14 at 21:08
@vadim123: Yes, I know. But telescoping is so much prettier, so I can not resist... :-) – Hans Apr 13 '14 at 21:23

score 0 · Answer 4 · answered Apr 13 '14 at 21:11

For the inductive step, assume $\sum\limits_{k=0}^n\ 2*3^{k-1} = 3^n-1$. You now want to somehow express this assumption in the $(n+1)th$ case. Notice that

$$\begin{array}{ccl} \sum\limits_{k=0}^{n+1}2*3^{k-1}&=&\sum\limits_{k=0}^n2*3^{k-1}+2*3^n\\ &=&3^n-1+2*3^n\\ &=&3^{n+1}-1 \end{array}$$

(The assumption is used in the second step.)

Therefore, the $nth$ case implies the $(n+1)th$ case.

score 0 · Answer 5 · answered Apr 13 '14 at 21:47

This is not true.

The sum starts with $2*3^{-1}$, so it includes a term $2/3$ for $k=0$, so the left side is not an integer and the right side is an integer.

I'm doing this as an answer because I am annoyed at the number of "proofs" of something that is false.

Prove that $\sum\limits_{k=0}^n\ 2\times3^{k-1} = 3^n-1$

5 Answers5