Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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! (:
Note: This problem requires strong induction instead of just weak induction. In weak induction, the hypothesis is that the statement holds for the previous value. But in strong induction, the hypothesis is that the statement holds for all preceding values that are still after the base case.
By induction hypothesis assume $C_n\le 4(n-1)^2$ for all $n<k$. Then
\begin{align*} C_k&=4C_{\lfloor k/2\rfloor}+k\\ &\le 4(\lfloor k/2\rfloor -1)^2+k\\ &\le 4\left(\frac{k}{2}-1\right)^2+k\\ &=k^2-4k+4+k\\ &=k^2-3k+4\\ &\le 4(k-1)^2 \end{align*}
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$
