Proving Big-O notation I need to prove, that $5n^2+7=O(2^n)$
I came up with the following proof, is this correct?
To prove this, we need to show $5n^2+7 \le c*2^n$ for $n \ge b$
We know, that $7\le n^2$ for ever $n\ge3$ (Can we just assume this or do we have to prove it?)
Thus, we get $5n^2 + n^2 < c*2^n$
After minimizing the left side, we get $6n^2 \le c*2^n$
We know, that $n^2 \le 2^n$ for every $n \ge 4$
Thus, we get $6*2^n \le c*2^n$ for every $n\ge4$
So we can conclude, that our b is 4 and our c is 6.
Is this proof correct?
 A: Your proof is correct, try to keep it as concise as possible though.
Choose $n_0 = 5$, $c = 6$, then $$5n^2 + 7 < 5n^2 + n^2 = 6n^2 < 6 \cdot 2^n,$$ so $$5n^2 + 7 \in \mathcal{O}(2^n).$$
A: Another way to prove this is:
We know that $$\lim_{n \rightarrow \infty} \frac{5n^2}{2^n}=0$$
Thus for $\epsilon=1,\exists n_1 \in \mathbb{N}$ such that: $$5n^2  <2^n, \forall n \geqslant n_1$$ where $C_1>0$.
Also we have that $$\lim_{n \rightarrow \infty} \frac{7}{2^n}=0$$
Thus for $\epsilon =1,\exists n_2 \in \mathbb{N}$ such that: $$7 < 2^n,\forall n_ \geqslant n_2$$
Thus for $n_0=\max\{n_1,n_2\}$ we have that $5n^2+7=O(2^n)+O(2^n)=O(2^n)$
A: Your proof is correct, and here is how I would write down your proof:$%
\require{begingroup}
\begingroup
\newcommand{\calc}{\begin{align} \quad &}
\newcommand{\op}[1]{\\ #1 \quad & \quad \unicode{x201c}}
\newcommand{\hints}[1]{\mbox{#1} \\ \quad & \quad \phantom{\unicode{x201c}} }
\newcommand{\hint}[1]{\mbox{#1} \unicode{x201d} \\ \quad & }
\newcommand{\endcalc}{\end{align}}
\newcommand{\Ref}[1]{\text{(#1)}}
\newcommand{\then}{\Rightarrow}
\newcommand{\when}{\Leftarrow}
\newcommand{\true}{\text{true}}
%$
$$\calc
    5n^2 + 7 = O(n^2)
\op=\hint{definition of $\;\cdot = O(\cdot)\;$}
    \langle \exists c : c>0 : \langle \forall_{l.e.} n :: 5n^2 + 7 \le c2^n \rangle \rangle
\op\when\hint{$\;7 \le n^2\;$ for $\;n \ge 3\;$}
    \langle \exists c : c>0 : \langle \forall_{l.e.} n :: 6n^2 \le c2^n \rangle \rangle
\op\when\hint{$\;n^2 \le 2^n\;$ for $\;n \ge 4\;$}
    \langle \exists c : c>0 : \langle \forall_{l.e.} n :: 6 \times 2^n \le c2^n \rangle \rangle
\op\when\hint{choose $\;c := 6\;$}
    \true
\endcalc$$
This uses the abbreviation 'for all large enough $\;n\;$': $$
\langle \forall_{l.e.} n :: P(n) \rangle \;\equiv\; \langle \exists b :: \langle \forall n : n \ge b : P(n) \rangle \rangle
$$ which (at least for me) make many proofs around complexity and big-$O$ easier to find and understand.
Whether or not you want to go further, and also prove that $\;7 \le n^2\;$ for $\;n \ge 3\;$, and that $\;n^2 \le 2^n\;$ for $\;n \ge 4\;$, depends on the context and what you are allowed to assume for your exercise/homework/assignment.
$%
\endgroup
%$
