While understanding big-O notation is important to understanding the statement I'm trying to prove anyone with a strong understanding of induction might be able to identify the mistake I made.
I attempted to complete a proof using induction, but made a mistake somewhere. While the statement I'm trying to prove is correct ($3n^{100}=O(2^n)$), my proof is invalid because I used fallacious constants for $c$ and $n_0$, meaning that the inequality I evaluated in my proof ($3k^{100}\le2^{100}\cdot2^k$ for all $k\ge1$) is flase. Basically, I ended up proving an false statement and don't know why. My proof is below.
Prove $ 3n^{100}=O(2^n)$
Using Induction I will show that $3k^{100}\le2^{100}\cdot2^k$ for all $k\ge1$
Base Case: I will show that $3k^{100}\le2^{100}\cdot2^k$ for $k=1$
$$LHS=3(1)^{100}=3\le2^{100}\cdot2^{(1)}=2^{101}=RHS$$
Induction Hypothesis: Assume that $3k^{100}\le2^{100}\cdot2^k$ for some $k\ge1$
Induction Step: I will show that $3(k+1)^{100}\le2^{100}\cdot2^{k+1}$
$$LHS=3(k+1)^{100}$$
$$\le3(k+k)^{100}=3(2k)^{100}$$
$$=2^{100}\cdot3k^{100}$$
$$\le2^{100}\cdot2^k \text{ (Using Induction Hypothesis)}$$
$$\le2^{100}\cdot2^{k+1}=RHS$$
I completed the proof, but when I double checked my work I found that from $k=3$ to around $k=850$ the expression $3k^{100}$ is actually less than $2^{100}\cdot2^k$. I can't figure out why my proof doesn't work. I know my proof could become valid if I choose a really big number for $c$ or $n_0$, but I'd rather understand where I went wrong than just choose random large constants until something works.
Best Answer
Assume that $~\displaystyle 3 \times \left[k^{100}\right] \leq 2^{100} \times 2^k.$
Then, as you indicated,
$$3 \times \left[(k+1)^{100}\right] \leq 3 \times \left[(2k)^{100}\right] = 2^{100} \times \left\{ ~3 \times \left[k^{100}\right] ~\right\}. \tag1 $$
Then, using the inductive hypothesis, against the RHS of (1) above, you have that
$$2^{100} \times \left\{ ~3 \times \left[k^{100}\right] ~\right\} \leq 2^{100} \times \left\{ ~2^{100} \times 2^k ~\right\} = 2^{\color{red}{200}} \times 2^k.$$
So, you have proven that
$$\text{If} ~~~~3 \times \left[k^{100}\right] \leq 2^{100} \times 2^k $$
$$\text{Then} ~~~~3 \times \left[(k+1)^{100}\right] \leq 2^{\color{red}{200}} \times 2^k.$$