4

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.

ViktorStein
  • 4,838
RedShift
  • 765
  • 3
  • 11
  • 28

2 Answers2

3

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

ViktorStein
  • 4,838
Alan
  • 16,582
1

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

Workaholic
  • 6,763