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! (:

  • $\begingroup$ 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$. $\endgroup$ – fleablood Feb 19 '18 at 1:37

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$

  • 1
    $\begingroup$ If the OP is novice to induction it might be worth pointing out that we doing strong induction where we show that P (n) for all n <k implies P (k), as opposed to what is probably the more familiar weak induction where we show P (n) implies P (n+1). $\endgroup$ – fleablood Feb 19 '18 at 1:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.