Need help with proof by induction, that $6n + 6 < 2^n$ for all $n > 5$

Question

Not sure how to even wrap my head around this, and want more practice in proofs by induction.

So I let P(n) be "$6n + 6 < 2^n$" and prove by induction that it holds true for all $n > 5$.

Base case is $n = 6$. Then $6(6) + 6 < 2^6$ or $42 < 64$ so that is true.

Inductive hypothesis is that we assume P(k) holds for an arbitrary $k > 5$.

Inductive step I'm kinda lost on. All I know is that I have to show P(k + 1). Not sure how I'm able to even visualise or manipulate the expression to get what I want. Stuff is lost on me and I learn best with step-by-step tutorials with explanations as to WHY something is, instead of just being told it is.

All I can think of is $6(k + 1) + 6 < 2^{k+1}$. That's all.

Answer 1

To show: $6(n+1) < 2^n ~: ~n > 5.$

Since the original poster discussed induction, I am assuming that it is intended that $n \in \Bbb{Z_{\geq 6}}$.

For $n=6, 6 \times 7 < 2^6.$

There are two standard approaches to complete the induction analysis, focusing on what happens, as $(n) \to (n+1).$

The answer of Martin Argerami focused on how much was being added to each side. This is one of the standard approaches.

The other approach, which focuses on how much each side is being multiplied by, is given below.

As $(n) \to (n+1),$ the expression $6(n+1)$ is multiplied by $~\displaystyle \frac{n+2}{n+1}~$ which is less than $(2)$.

As $(n) \to (n+1),$ the expression $2^{n}$ is multiplied by $(2)$.

So, the LHS is multiplied by a smaller factor than the RHS. Therefore, if, for a given value of $(n)$, the LHS is smaller than the RHS, this inequality must also hold, as $(n)$ goes to $(n+1).$

Answer 2

As part of the induction step, we assume the following to be true: $$6k+6 < 2^k$$

Since this is assumed to be true, we can manipulate it in any way that retains the inequality. For instance, we can multiply both sides by $2$ to turn that $2^k$ into a $2^{k+1}$: $$12k+12 = 2(6k+6)<2(2^k) = 2^{k+1}$$

We want to compare this to $6(k+1)+6 = 6k+12$, so let's rewrite this inequality as $$6k+(6k+12) < 2^{k+1}$$

and here, we're finished, because $6k > 0,$ so $$6k+12 < 6k+(6k+12) < 2^{k+1}.$$

---

The above can now be condensed into a single set of inequalities as $$6(k+1)+6 = 6k+12 < 12k+12 = 2(6k+6) < 2(2^k) = 2^{k+1}$$