# Example

Prove that $3^n > 2n$ for every positive integer $n$

Let us argue by induction...

Starting with the basis step, we must show that the statement holds for the smallest value of $n$ that we wish to consider.

Since we seek to prove the statement holds for every positive integer, then the smallest value we wish to consider would be $n=1$.

When $n=1$, the statement reduces to $3^1 > 2 \cdot 1$, which of course, is true.

Now we proceed with the inductive step, where we must show that if we know the statement holds for some particular value of $n$, say $n=k$, then the statement must also hold when $n=k+1$.

Equivalently, for this problem, we need to show that if the following "inductive hypothesis" is true for some particular value of $k$ $$3^k > 2k$$ then, it must also be true that $$3^{k+1} > 2(k+1)$$

To demonstrate this last inequality, we will attempt to create a string of equalities/inequalities that starts at $3^{k+1}$ and terminates at $2(k+1)$, like the following: $$3^{k+1} = \cdots > \cdots = \cdots \geq \cdots = 2(k+1)$$ Note: as long as there is one strict inequality symbol in the string that we generate, we will be able to conclude $3^{k+1} > 2(k+1)$.

To begin, let us separate a factor of $3$ from $3^{k+1}$ to give us an opportunity to use our inductive hypothesis (which is a statement about $3^k$):

$$3^{k+1} = 3 \cdot 3^k \quad \cdots \quad ? \quad \cdots \quad 2(k+1)$$

Our inductive hypothesis assures us that $3^k > 2k$, so

$$3^{k+1} = 3 \cdot 3^k > 3 \cdot (2k) \quad \cdots \quad ? \quad \cdots \quad 2(k+1)$$

$$3^{k+1} = 3 \cdot 3^k > 3 \cdot (2k) = 6k \quad \cdots \quad ? \quad \cdots \quad 2k+2 = 2(k+1)$$

If we knew $6k \geq 2k+2$, we would be done, right? This, fortunately, can be quickly deduced from the fact that $k$ is a particular value of $n$, and the only values of $n$ we are considering are positive integers. Consequently,

$$\begin{array}{rcl} k \geq 1 &\Rightarrow& 2k \geq 1\\\\ &\Rightarrow& 4k \geq 2\\\\ &\Rightarrow& 6k \geq 2k+2 \end{array}$$

So,

$$3^{k+1} = 3 \cdot 3^k > 3 \cdot (2k) = 6k \geq 2k+2 = 2(k+1)$$

and hence,

$$3^{k+1} > 2(k+1)$$

which is what we needed to show.

Having met with success in both the basis and inductive steps, we are free to conclude by the principle of mathematical induction, that the following is true for every positive integer $n$

$$3^n > 2n$$ QED.

Here is another, more elegant way to demonstrate the inductive step above:

Recall that $k$ is a particular value of $n$, and the only values of $n$ that are being considered are positive integers, so $k \geq 1$. As such,

$$3^k > 1$$

But then,

$$2 \cdot 3^k > 2$$

Now, adding this inequality to our inductive hypothesis

$$3^k > 2k$$ we arrive at $$3 \cdot 3^k > 2k + 2$$

or equivalently,

$$3^{k+1} > 2(k+1)$$

which is what was needed to show to complete the inductive step

$\ddot\smile$