<s>[INST] Proof by induction: $f(n) < g(n)$. I have just started learning how to do proof by induction, and no amount of YouTube and stack exchange has led me to work this question out.
Given two functions $f$ and $g$, let $n \in \mathbb{N}$ such that
$$f(n) = 2n + 1$$
and
$$g(n) = \frac{n^3}{3} - n - 2.$$
We assume that $f(n) < g(n)$ for all $n \ge 4$.
The basis step is straight forward, for $n=4$. It results in $9 < 15.33$, but for the inductive step, I can't figure out how to go about it.
The inductive hypothesis would be: If
$$2n + 1 < \frac{n^3}{3} - n - 2$$
Then
$$2(n+1) + 1 < \frac{(n+1)^3}{3} - (n+1) - 2.$$
Could anyone please give me an idea of how one would prove that? Any help would be much appreciated!
 [/INST] Please let me know if this is correct.
Assuming: $2n + 1 < \frac{1}{3}n^3 - n - 2$
Prove: $2(n+1) + 1 < \frac{1}{3}(n+1)^3 - (n+1) - 2$
RHS:
$2(n+1) + 1 = 2n + 1 + 2$
We know, by the assumption, that this is $< \frac{1}{3}n^3 - n - 2 + 2$, simplified to $< \frac{1}{3}n^3 - n$
We can also see that $\frac{1}{3}n^3 - n < \frac{1}{3}(n+1)^3 - n - 1$
Therefore, we can conclude that
$2n + 1 + 2 < \frac{1}{3}(n+1)^3 - n - 1$
Therefore we prove that
$2(n+1) + 1 < \frac{1}{3}(n+1)^3 - (n+1) - 2$ ​□
</s>