Lower bound on $c_n = 4c_{\lfloor n/2 \rfloor} + n$
Let's start with the case $n = 2^k$. We have
\begin{align}
c_{2^k} &amp;= 2^k + 4c_{2^{k-1}} \\ &amp;= 2^k + 4 \cdot 2^{k-1} + 16c_{2^{k-2}} \\ &amp;= \cdots \\ &amp;= 2^k + 4 \cdot 2^{k-1} + 4^2 \cdot 2^{k-2} + \cdots + 4^{k-1} \cdot 2^1 + 4^k c_1 \\ &amp;= 2^k + 4 \cdot 2^{k-1} + 4^2 \cdot 2^{k-2} + \cdots + 4^{k-1} \cdot 2 = \\ &amp;= 2^k(1 + 2 + 2^2 + \cdots + 2^{k-1}) \\ &amp;= 2^k(2^k-1).
\end{align}
It is easy to prove by induction that the sequence $c_n$ is monotone. Therefore, if $2^k \leq n &lt; 2^{k+1}$,
$$
c_n \geq c_{2^k} = 2^k(2^k-1) &gt; \frac{n}{2}\left(\frac{n}{2}-1\right).
$$
Now
$$
\frac{n}{2}\left(\frac{n}{2}-1\right) \geq \frac{(n+1)^2}{8} \Longleftrightarrow
2n(n-2) \geq (n+1)^2 \Longleftrightarrow n^2 \geq 6n + 1.
$$
This holds for all $n \geq 7$. You can check that your inequality holds for $n=2,3,4,5,6$ directly.

You can also likely prove the inequality directly by induction, but the argument above is more similar to stuff you might actually see later on. The idea is that we find a specific type of $n$ for which $c_n$ is particular easy to calculate and to compare to $n$, and then we try to understand $c_n$ for all $n$ using these specific values.