Induction with Inequalities Suppose that we are trying to prove that $2^n > 10n + 9 $ $\forall n \geq 9$
Basis: $2^9 > 99$ is true.
Inductive Hypothesis: Assume that it is true that $n=k$ $\forall n \geq 9$
Then: $2^k > 10k + 9 $
Inductive step: Prove for $n=k+1$: $$2^{(k+1)} > 10(k+1) + 9 $$
This is where I get confused. Is it true that: $$2^{(k+1)} = 2^k\cdot 2 = 2^k +2^k > 2^k+2 > 10(k+1) +9$$
Is this how I string this inductive proof together? I feel  like there is a gap in my understanding of whether or not this statement is true.
 A: You have a flaw in your chain.   All you can relate is using the inductive hypothesis that $$2^k>10k+9$$,  so you have
$$2^{k+1}=2^k\cdot 2=2^k+2^k$$
now, you can add the inductive hypothesis to itself to get
$$2^k+2^k>10k+9+10k+9$$
Keep in mind, what we want it to be bigger than is $10(k+1)+9$,  so all that is left is to show what we have is bigger than that.  One way is to change the $9+9$ to $10+8$ in what we have, so we can then factor to get that magic $10(k+1)$ term:
$$2^k+2^k>10k+9+10k+9=10k+10+10k+8=10(k+1)+10k+8$$
So, we are left with needing that $10k+8\ge9$, which it is, since $k\ge 9$.
A: It is not clear to me how you managed to get $10(k+1)+9$ at the end. Instead of using, $2^k+2^k\gt2^k+\color{red}{2}$, choose a convenient number $m$ that satisfies $2^k\gt m$ (for that first inequality to be true), as well as $m\gt 10$, since $10k+9+\color{green}{10}=10(k+1)+9$. Once done, start off with the inductive assumption, namely, $2^k\gt 10k+9$, then add to both sides that number to get, $$2^k+m\gt 10k+9+m,$$ and since $m\gt10$ and $2^k\gt m$ it follows that $$2^k+2^k\gt 2^k+m\gt 10k+9+m\gt10k+9+10.$$
