Proving Big-Theta bound Prove by induction that $$ \frac{n^2}{2} + 3n + \ln(n) \in \Theta (n^2).$$
This my attempt.
Base case ($n=1$):$\frac{7}{2} \in \Theta(1)$ is true.
Inductive step: Assume $\frac{n^2}{2} + 3n + \ln(n) \in \Theta (n^2) $ is true for some $n \in \mathbb N$. Then we have that there is $c$ and $n_0$ s.t. $\frac{n^2}{2}+3n +\ln(n) \leq c n^2$ for $n \geq n_0$. We also have $\frac{(n+1)^2}{2} + 3(n+1) + \ln (n+1) = \frac{n^2}{2} +3n + \ln(n) + n + \frac{7}{2} + \ln(\frac{n+1}{n})\leq cn^2 + n + \ln(\frac{n+1}{n}).$ What else can I do?

Continuing off from where you were, since $\ln(\frac{n+1}{n}) \leq n$, we have that $cn^2+n+\ln(\frac{n+1}{n})\leq cn^2+2n$. WLOG assume $c>1$ and we have $cn^2+2n\leq cn^2+2cn+c=c(n+1)^2$. Proven as required.
Sorry for the poor formatting I’m on my phone waiting for breakfast at a hotel.
