Prove that $C_n < 4n^2$ for all n greater than or equal to 1 $C_1 = 0$, $C_n = C_{\lfloor n/2\rfloor} + n^2$ for all $n \ge 1$
Prove that $C_n < 4n^2$ for all $n \ge 1$.
I don't know how to even approach this. I remember something about inductive proofs...but i really don't understand that, could you please explain that to me?

Why not unroll the recursion to get a precise answer? 
Let $$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k$$
be the binary representation of $n.$
This yields the exact formula
$$C_n = \sum_{k=0}^{\lfloor \log_2 n \rfloor - 1} 
\left(\sum_{j=k}^{\lfloor \log_2 n \rfloor} d_j 2^{j-k}\right)^2$$
where $n\ge 2$ and zero otherwise.
Clearly this is maximized when all digits are equal to one, giving
$$C_n\le \sum_{k=0}^{\lfloor \log_2 n \rfloor - 1} 
\left(\sum_{j=k}^{\lfloor \log_2 n \rfloor} 2^{j-k}\right)^2
= \frac{16}{3} 2^{2 \lfloor \log_2 n \rfloor} 
- 8 \times 2^{\lfloor \log_2 n \rfloor} + \lfloor \log_2 n \rfloor
+ \frac{8}{3}.  $$
For a string of ones we have $n=2^j-1$ for some $j$ with $j-1 =  \lfloor \log_2 n \rfloor.$ This gives
$$2^{\lfloor \log_2 n \rfloor} = \frac{1}{2} (n+1)
\quad\text{or}\quad
\lfloor \log_2 n \rfloor = \log_2(n+1) - 1.$$
Hence we have the following bound on the leading term
$$ \frac{16}{3} 2^{2 \lfloor \log_2 n \rfloor} 
= \frac{16}{3} 2^{2 \log_2(n+1) - 2}
= \frac{4}{3} (n+1)^2.$$
Furthermore recalling the condition on $n$ we have
$$- 8 \times 2^{\lfloor \log_2 n \rfloor} = -8 \times \frac{1}{2} (n+1).$$
Putting these pieces together we find that
$$C_n\le \frac{4}{3}n^2-\frac{4}{3}n + \lfloor \log_2 n \rfloor
<  \frac{4}{3}n^2$$
because we certainly have $4/3 \times n > \log_2 n.$
To conclude, let us briefly consider the lower bound, which occurs when there is a one followed by a string of zeros, giving
$$C_n\ge \sum_{k=0}^{\lfloor \log_2 n \rfloor - 1} 
\left(2^{\lfloor \log_2 n \rfloor - k}\right)^2
= \frac{4}{3} 2^{2\lfloor \log_2 n \rfloor} -\frac{4}{3}.$$
In this scenario we have $\lfloor \log_2 n \rfloor = \log_2 n,$ so that the lower bound gives $$C_n\ge  \frac{4}{3} n^2 -\frac{4}{3}.$$
Note that the bounds from the two bit patterns are no longer directly comparable because the substitutions for $\lfloor \log_2 n \rfloor$ are different. What we may say, however, is that $$C_n \sim \frac{4}{3} n^2.$$
The coefficient on the leading term of the bounds in $\lfloor \log_2 n \rfloor$ fluctuates between $4/3$ and $16/3$ on each interval where $\lfloor \log_2 n \rfloor$ is constant. However when we reach the end of this interval $\lfloor \log_2 n \rfloor$ is off by almost one from the true value, reducing $16/3$ to $4/3$ when the bounds are expressed in $n.$ 
This link points to a series of similar calculations.
