# Discrete Math Informal Proofs Using Mathematical Induction

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):

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

## 2 Answers

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

• so when your verifying it your justifying? – Patrick William McCully Apr 29 '15 at 16:04
• 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. – nSheahan Apr 29 '15 at 16:19

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.