2
$\begingroup$

Need to do a proof by mathematical induction using 4 steps to show that the following statement is true for every positive integer n and to help use the weak principle of mathematical induction. $2 + 6 + 18 + ... + 2\times{3^{n-1}} = 3^n-1$

  1. show that the base step is true

  2. What is the inductive hypothesis?

  3. what do we have to show?

  4. proof proper (Justify each step):

$\endgroup$
  • $\begingroup$ I'm confused. Do you mean $$2 + 6 + ... + 2\cdot 3^{n-1} = 3^{-1}$$ This is how I interpret the question as written. $\endgroup$ – nSheahan Apr 29 '15 at 14:56
  • $\begingroup$ there I fixed it $\endgroup$ – Patrick William McCully Apr 29 '15 at 15:03
  • 1
    $\begingroup$ Hint: words in the title are allowed to be in lower case. $\endgroup$ – Marc van Leeuwen Apr 29 '15 at 15:45
1
$\begingroup$

Base Step: $2 \cdot 3^{1-1} = 2 = 3^1 - 1$

The inductive hypothesis is: $\sum_{n=1}^{k} 2 \cdot 3^{n-1} = 3^k - 1$

We must show that under the assumption of the inductive hypothesis that $$3^k - 1 + 2 \cdot 3^k = 3^{k + 1} - 1$$

We verify this as $$3^k - 1 + 2 \cdot 3^k = 3^k(1 + 2) - 1$$ $$= 3^{k+1} - 1$$

$\endgroup$
  • $\begingroup$ so when your verifying it your justifying? $\endgroup$ – Patrick William McCully Apr 29 '15 at 16:04
  • $\begingroup$ Partially. The whole proof is my justification. I perform justification in several parts. One step is the base case. Another is my hypothesis and yet another is the verification that when we assume the hypothesis we can show $P(n) \rightarrow P(n+1)$. I hope this helps. If you have any other questions feel free to ask. $\endgroup$ – nSheahan Apr 29 '15 at 16:19
0
$\begingroup$

Hint $\ $ By a very simple transformation we can reduce the induction to a very trivial induction, namely if $\,g(n)\,$ is constant $\,g(n\!+\!1)=g(n)\,$ then $\,g(n) = g(0)\,$

The $\rm\ RHS$ and $\rm LHS$ have equal first difference $\,f(n\!+\!1)-f(n) = 2\cdot 3^n,\,$ therefore defining $\,g(n) := \rm RHS - LHS$ $\Rightarrow$ $\,\color{#c00}{g(n\!+\!1)-g(n) = 0},\ g(0) = 0,\,$ so an obvious induction shows that $\,g(n) = 0\,$ for all $\,n,\,$ i.e. $\,\color{#0a0}{g(n)=0}\,\Rightarrow\,$ $\,g(n\!+\!1) = \color{#c00}{g(n\!+\!1)-g(n)} + \color{#0a0}{g(n)} = \color{#c00}0 + \color{#0a0}0 = 0.\ $ Therefore, for all $\,n\,$ we have $\,g(n) =\rm RHS - LHS = 0,\,$ i.e. $\rm RHS = LHS.\ $ QED

Remark $\ $ This is a prototypical case of telescopic induction, which often serves to greatly simplify inductive proofs. The above transformation essentially shows that both sides equal $\,\sum 2\cdot 3^k,\,$ by rewriting them as a (telescopic) sum of their first differences $\,\sum\,(f_{k+1}\!-f_k).\,$ For many further examples of telescopy see here.

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