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!
 A: 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$ ​□
A: The putative inequality can also be re-arranged as
$$ 2n \ + \ 1 \ \ <^{?} \ \ \frac{n^3}{3} \ - \ n \ - \ 2 \ \ \Rightarrow \ \ 6n + 3 \ \ <^{?} \ \ n^3  - 3n - 6 $$ $$ \Rightarrow \ \ 9 \ \ <^{?} \ \ n^3  - 9n \ \ = \ \ (n - 3)·n·(n+3) \ \ , $$
which makes it easier to see that, for natural numbers, the smallest value of $ \ n \ $ that works is $ \ n  \ = \ 4 \ \ . $  (In fact, this makes me suspicious that the poser of the problem constructed the given functions starting from an expression rather like this.)
The induction would then proceed from taking $ \ 9 \  <  \  (k - 3)·k·(k+3) \ $ to be true to producing the successive statement
$$   9 \ \  <^{?}  \ \ ( \ [k+1] \ - \ 3 \ ) \ · \ [k+1] \ ·\ ( \ [k+1] \ + \ 3 \ ) \ \ . $$
We can then write
$$   9 \ \  <  \ \ (k - 3)·k·(k+3) \ \ < \ \ (k - 3)·k·(k+3) \ · \ \frac{k-2}{k-3} \ · \ \frac{k+1}{k} \ · \ \frac{k+4}{k+3} $$ $$ = \ \  ( k - 2 ) \ · \ (k + 1) \ ·\ (k + 4) \ \ , $$
which is certainly true since each of the multiplicative ratios is greater than $ \ 1 \ \ . $  Hence $ \ f(n) \ < \ g(n) \ \ $ for natural numbers $ \ n \ \ge \ 4 \ \  . $
A: The key idea is to calculate and compare the differences $f(n+1)-f(n)$ and $g(n+1)-g(n)$. If you know that $f(n)<g(n)$ and also $f(n+1)-f(n)\leq g(n+1)-g(n)$, then it follows that $f(n+1)<g(n+1)$, which is what you want.
