I am doing questions from past exams and I stumbled upon this one. I have no idea how to go about solving it.I never had any logarithmic functions in my previous bigOh proofs nor have I had to use induction in them. Sorry about the difficulty in formatting, I would post some of my work but I think I got nowhere with it.
It reads:
Prove that $$ \left(\sqrt{2}\right)^{\log n} + \log^2 n + n^{10} = O(2^n). $$ There is at least one non-trivial induction to do as part of the overall proof.
There is no need to use induction. I'm assuming that $\log = \log_e$. First note that $\sqrt{2}^{\log n} \leq e^{\log n} \leq n$. Also, the Taylor expansion of $e^x$ shows that $e^x \geq 1+x$ and so $e^{n-1} \geq n$, implying $\log n \leq n-1$. This shows that $\sqrt{2}^{\log n} + \log^2 n + n^{10} \leq n+n^2+n^{10} \leq 3n^{10}$. Now we can use l'Hôpital's rule repetitively: $$ \lim_{n\to\infty} \frac{3n^{10}}{2^n} = \lim_{n\to\infty} \frac{30n^9}{2^n \log 2} = \lim_{n\to\infty} \frac{270n^8}{2^n \log^2 2} = \cdots = \lim_{n\to\infty} \frac{3\cdot 10!}{2^n \log^{10} 2} = 0. $$