Induction proof that if $C_1 = 0$ and $C_n = 4C_{\lfloor n/2 \rfloor} + n$ then $C_n \le 4(n-1)^2$

Question

$C_1 = 0$, $C_n = 4C_{\lfloor n/2 \rfloor} + n$

Prove that $Cn$ less than or equal to $4(n - 1)^2$

What I did:

Base step: n = 1

$C1$ <= $4(1 - 1)^2$

0 <= 0 therefore true

how do you do the induction step?

Answer 1

$c_1=0\leq 4(1-1)^2=0$.

Suppose that this stands for every $c_i$ ,$i\leq n$,i will show that it stands for $c_{n+1}$.

$c_{n+1}=4c_{[\frac {n+1}{2}]}+n+1\leq 16([\frac {n+1}{2}]-1)^2+n+1\leq 4(n-1)^2+n+1=4n^2-8n+4+n+1=4n^2-7n+5<4n^2=4((n+1)-1)^2$