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

$$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?

$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$