3
$\begingroup$

Use weak induction to prove the following statement is true for every positive integer $n$: $$2+6+18+\dots+2\cdot 3^{n-1}=3^n-1$$ Base Step: Prove it is true for $n$.

Inductive Hypothesis: It will be true for $n+1$

What I need to show: That it will be true for n and n+1

Proof Proper:.....

To get this started, how do I prove that it is true for $n$? What $n$ do I choose? The fact that there is a "..." in the equation scares me. How do I know how to quantify $n$ and $n+1$?

$\endgroup$
3
$\begingroup$

The base case is typically the least value of $n$ for which you are proving an assertion applies. Since we are aiming to prove $$P(n):\quad 2+6+18 + \cdots + 2\cdot 3^{n-1}=3^n-1 \tag{P(n)}$$ holds for all positive integers $n$, we need to prove that $P(n)$ holds for $n \geq 1$, and so we need first to confirm that $P(n)$ holds for the base case $n = 1$.

Base Case:

$P(1)\; (n = 1): {\bf 2\cdot 3^{1-1}} = 2\cdot 3^0 = 2 = {\bf 3^1 - 1}\tag{base case: True}$

Inductive Hypothesis (IH)

Now, we assume that $P(k)$ is true for some arbitrary positive integer $n = k$. That is, we assume that it is true that $P(k):\quad 2 + 6 + 18 + \cdots + 2\cdot 3^{k-1}=3^k-1\tag{IH}$

Inductive Step Now, we will use our inductive hypothesis (IH) to prove that $P(k) \implies P(k+1)$. So our aim is to show, using the inductive hypothesis, that $2 + 6 + 18 + \cdots + 2\cdot 3^{k} =3^{k + 1}-1$:

$$\begin{align} P(k + 1):\quad \underbrace{2 + 6 + 18 + \cdots + 2\cdot 3^{k - 1}}_{= \,\large 3^k - 1,\;by \;\text{IH}} + 2\cdot 3^{k} & = (3^k - 1) + 2\cdot 3^k \\ \\ & = 3\cdot 3^k - 1 \\ \\ & = 3^{k + 1} - 1\end{align}$$

So we have shown, in this third step, that $P(k) \implies P(k+1)$.

Hence, by induction on $n$, we can conclude that $P(n)$ is true for all integers $n \geq 1$

$\endgroup$
  • $\begingroup$ we have both had issues with this, so very interesting and on-point: meta.math.stackexchange.com/questions/10133/… $\endgroup$ – Amzoti Jul 7 '13 at 4:17
  • $\begingroup$ @amWhy: Where are you right now? I see you are flying beyond the Heaven clouds.:-) $\endgroup$ – mrs Jul 7 '13 at 11:46
  • $\begingroup$ Hello, @Babak Here I am! $\endgroup$ – Namaste Jul 7 '13 at 11:48
1
$\begingroup$

Don't let the "$\dots$" scare you. Here, it just means, "continue the pattern until you get to $2\cdot 3^{n-1}$".

  • For $n=4$, "$2+6+18+\cdots+2\cdot 3^{n-1}$" means $2+6+18+54$. (Stop at $2\cdot 3^{4-1}$.)
  • For $n=5$, "$2+6+18+\cdots+2\cdot 3^{n-1}$" means $2+6+18+54+162$. (Stop at $2\cdot 3^{5-1}$.)
  • For $n=10$, "$2+6+18+\cdots+2\cdot 3^{n-1}$" means $$2+6+18+54+162+486+1458+4374+13122+39366$$
  • For $n=100$, it's just best to leave it as $2+6+18+\cdots+2\cdot 3^{100-1}$. By the way, this gets at the importance of formulas like the one you're proving; the "$\cdots$" notation allows us to abbreviate a sum with dozens, hundreds, zillions of terms, but that's just sweeping the computation under the rug; the $3^n-1$ on the formula's right-hand side tells us that this crazy-long sum can be computed in just two terms. How convenient!

(Note that for $n=3$, $2$, or $1$, the sum stops at the "$18$", the "$6$", or just that first "$2$". In these cases, there are more terms visible than are actually used in the sums. Consider that a quirk of the notation.)


Now, to solve the problem ... Forget about induction for a moment. Suppose I tell you that the formula works for $n=1,000,000$. That is, I assert that $$2 + 6 + 18 + \cdots (999,995 \text{ terms}) \cdots + 2\cdot 3^{999,999} = 3^{1,000,000} - 1 \qquad (\star)$$ The numbers involved are too large for you to verify directly, so you'll have to take my word for it. Based on that word, can you prove that we can push $n$ one step higher? $$2 + 6 + 18 + \cdots (999,996 \text{ terms}) \cdots + 2\cdot 3^{1,000,000} \stackrel{?}{=} 3^{1,000,001} - 1 \qquad (\star\star)$$ Well, did you notice that the number of hidden terms got bigger? That's because the "$\cdots$" part of $(\star\star)$ includes the "$\cdots$" part of $(\star)$ as well as $2\cdot 3^{999,999}$, which was the last term in $(\star)$, but has become the next-to-last term in $(\star\star)$. So, we can write: $$2 + 6 + 18 + \cdots (999,995 \text{ terms}) \cdots + 2\cdot 3^{999,999} + 2\cdot 3^{1,000,000} \stackrel{?}{=} 3^{1,000,001} - 1 \qquad (\star\star\star)$$ But, hey, I told you in $(\star)$ ---and you believed me, right?--- that the sum from $2$ up to $2\cdot 3^{999,999}$ has a much shorter form; therefore, $$\left( \;\; 3^{1,000,000} - 1 \;\; \right) + 2\cdot 3^{1,000,000} \stackrel{?}{=} 3^{1,000,001} - 1 \qquad (\star\star\cdots\star)$$ Of course, no self-respecting algebra student would leave the left-hand side the way it is. Let's combine the $3^{1,000,000}$ terms, and ... voila! $$2\cdot 3^{1,000,000} + 3^{1,000,000} - 1 = \left( 2 + 1 \right) \cdot 3^{1,000,000} - 1 = 3 \cdot 3^{1,000,000} - 1 \stackrel{\ddot\smile}{=} 3^{1,000,001} - 1$$


The thing is, there's nothing special about $1,000,000$ in the above argument. I could've asserted that the formula worked for any value of $n$ that I liked, and we could've used identical logic to show that the formula works for the next $n$. Using $1,000,000$ just gives you a specific "any value" to wrap your brain around. The number is big enough to keep you from even considering directly computing anything, so that you can focus on how to push "one higher"; and it's unusual enough to stick out in the argument, making it easy to convert your logic into an official "inductive step": simply replace all "$1,000,000$"s (and nearby values) with the generic "$n$" (and "$n\pm 1$", etc, as appropriate).

  • Case $n$ (asserted): $2+6+18+\cdots + 2\cdot 3^{n-1} = 2\cdot 3^{n}-1\quad$(compare with $(\star)$)
  • Case $n+1$ (to be shown): $2+6+18+\cdots + 2\cdot 3^{n} \stackrel{?}{=} 2\cdot 3^{n+1}-1\quad$(compare with $(\star\star)$)
  • Proof of Case $n+1$ using Case $n$: $$\begin{align} 2+6+18+\cdots + 2\cdot 3^{n} &= 2+6+18+\cdots + 2\cdot 3^{n-1} + 2\cdot 3^{n} \\ &= \left(\;\; 3^{n}-1 \;\;\right) + 2\cdot 3^{n} \\ &= (2+1)\cdot 3^n - 1 \\ &\stackrel{\ddot\smile}{=} 3^{n+1} - 1 \end{align}$$

So, now we've built a magic induction machine that will spread the validity of the formula from any $n$ to the next $n$. We just have to feed the machine a first $n$ ---that is, the first $n$--- by proving that the formula holds in the dead-simple case of $n=1$.

  • Case $1$: $\quad 2\cdot 3^{1-1} \stackrel{?}{=} 3^{1}-1$
  • (Overly-pedantic*) Proof of Case $1$: $\quad 2\cdot 3^{1-1} = 2 \cdot 3^0 = 2 \cdot 1 = 2 = 3 - 1 \stackrel{\ddot\smile}{=} 3^1-1$

*In real mathematical life (as opposed to imaginary mathematical life?), we usually just say "The base case is obvious."

And there you have it. Thanks to our magic induction machine, what's true for $n=1$ is true for $n=2$; and what's true for $n=2$ is true for $n=3$; and what's true for $n=3$ is true for $n=4$; and so on, and so on, and so on.

$\endgroup$
0
$\begingroup$

Let $P(n): 2+6+18+\cdots+2(3^{n-1})=3^n-1$

So, $P(1):2= 3^1-1$ which is true

Let $P(m)$ is true i.e., $2+6+18+\cdots+2(3^{m-1})=3^m-1$

$P(m+1):$ $2+6+18+\cdots+2(3^{m-1})+2\cdot 3^m=3^m-1+2\cdot 3^m=(1+2)3^m-1=3^{m+1}-1$

So, $P(m+1)$ will hole true if $P(m)$ is true

But, we have already shown $P(n)$ is true for $n=1$

$\endgroup$
0
$\begingroup$

The "base step" isn't to prove that it is true for "$n$"... it is to prove that it is true for the first positive integer.

So, in this case, you want to start off by proving that it is true for $n=1$; that is, that $2=3^1-1$. (Not too hard of a base case, right?)

Now, the idea is this: ASSUMING that for some number $n$ you know it is true, show that it is also true for the next number.

$\endgroup$
0
$\begingroup$

If you needn't insist on applying the mathematical induction, there exists another proof for this which is more simple.

Let $$S_n=\sum_{k=1}^{n}2 \cdot 3^{k-1}=2+6+18+\dots+2\cdot 3^{n-1}.$$Then, we obtain $$3S_n=\sum_{k=1}^{n}2 \cdot 3^{k}=6+18+54+\dots+2\cdot 3^{n}.$$ The one below minus the above gives that $$2S_n=2 \cdot 3^{n}-2.$$As a result,$$S_n=3^n-1.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.