Discrete Math Informal Proofs Using Mathematical Induction

Question

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

Answer 1

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

Answer 2

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.