# Recursive Induction Floor Proof Help

I've been trying to figure out this but I don't know how to tackle the inductive process,

So I have numbers defined recursively as it follows:

For $C_1=0$ and for $n>1$

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

Where $\lfloor n/2 \rfloor$ is the floor function.

After that definition, I have to prove that

$$C_n \le4(n-1)^2 \ \forall n \in \mathbb N$$

I already proved for the base $C_1$, but I don't know how to approach it from there. Thanks any help! (:

• Hint: do strong induction. It's not just that $C_n\le 4 (n-1)^2$ that you are assuming. You are also assuming that as $\frac {n+1}2 \le n$ that $C_{[\frac {n+1}2]}\le 4 ([\frac {n+1}2])^2$. Feb 19, 2018 at 1:37

By induction hypothesis assume $C_n\le 4(n-1)^2$ for all $n<k$. Then
for all $k\ge 2$. To show the final step, consider the difference $$4(k-1)^2-(k^2-3k+4)=k(3k-5)$$
which is clearly positive for all $k\ge 2$