Prove that $C_n < 4n^2$ for all n greater than or equal to 1 $C_1 = 0$, $C_n = C_{\lfloor n/2\rfloor} + n^2$ for all $n \ge 1$
Prove that $C_n < 4n^2$ for all $n \ge 1$.
I don't know how to even approach this. I remember something about inductive proofs...but i really don't understand that, could you please explain that to me?
 A: Induction is the key indeed.
Observe that the claim is false for $n=0$.
We can start the induction with noting that $C_1=C_0+1^2=1<4\cdot 1^2$.
Now consider $n\ge2$ and assume that we already knwo that $C_k<4k^2$ for all integers $k$ with $1\le k<n$.
From $n\ge2$ we obtain that $1\le \lfloor \frac n2\rfloor\le\frac n2<n$, hence the induction hypothesis applies to $k=\lfloor \frac n2\rfloor$. This gives us
$C_n= C_k+n^2<4k^2+n^2\le 4\cdot(\frac n2)^2+n^2=2n^2<4n^2$.
By revisitin the proof, we see that we can show the sharper inequality $C_n<\kappa n^2$ as long as $\kappa\ge \frac14$ (for the base step) and $\frac \kappa 4+1\le \kappa$. In other words, we can as well show $C_n<\frac43n^2$ for all $n\ge 1$.
A: Why not unroll the recursion to get a precise answer? 
Let $$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k$$
be the binary representation of $n.$
This yields the exact formula
$$C_n = \sum_{k=0}^{\lfloor \log_2 n \rfloor - 1} 
\left(\sum_{j=k}^{\lfloor \log_2 n \rfloor} d_j 2^{j-k}\right)^2$$
where $n\ge 2$ and zero otherwise.
Clearly this is maximized when all digits are equal to one, giving
$$C_n\le \sum_{k=0}^{\lfloor \log_2 n \rfloor - 1} 
\left(\sum_{j=k}^{\lfloor \log_2 n \rfloor} 2^{j-k}\right)^2
= \frac{16}{3} 2^{2 \lfloor \log_2 n \rfloor} 
- 8 \times 2^{\lfloor \log_2 n \rfloor} + \lfloor \log_2 n \rfloor
+ \frac{8}{3}.  $$
For a string of ones we have $n=2^j-1$ for some $j$ with $j-1 =  \lfloor \log_2 n \rfloor.$ This gives
$$2^{\lfloor \log_2 n \rfloor} = \frac{1}{2} (n+1)
\quad\text{or}\quad
\lfloor \log_2 n \rfloor = \log_2(n+1) - 1.$$
Hence we have the following bound on the leading term
$$ \frac{16}{3} 2^{2 \lfloor \log_2 n \rfloor} 
= \frac{16}{3} 2^{2 \log_2(n+1) - 2}
= \frac{4}{3} (n+1)^2.$$
Furthermore recalling the condition on $n$ we have
$$- 8 \times 2^{\lfloor \log_2 n \rfloor} = -8 \times \frac{1}{2} (n+1).$$
Putting these pieces together we find that
$$C_n\le \frac{4}{3}n^2-\frac{4}{3}n + \lfloor \log_2 n \rfloor
<  \frac{4}{3}n^2$$
because we certainly have $4/3 \times n > \log_2 n.$
To conclude, let us briefly consider the lower bound, which occurs when there is a one followed by a string of zeros, giving
$$C_n\ge \sum_{k=0}^{\lfloor \log_2 n \rfloor - 1} 
\left(2^{\lfloor \log_2 n \rfloor - k}\right)^2
= \frac{4}{3} 2^{2\lfloor \log_2 n \rfloor} -\frac{4}{3}.$$
In this scenario we have $\lfloor \log_2 n \rfloor = \log_2 n,$ so that the lower bound gives $$C_n\ge  \frac{4}{3} n^2 -\frac{4}{3}.$$
Note that the bounds from the two bit patterns are no longer directly comparable because the substitutions for $\lfloor \log_2 n \rfloor$ are different. What we may say, however, is that $$C_n \sim \frac{4}{3} n^2.$$
The coefficient on the leading term of the bounds in $\lfloor \log_2 n \rfloor$ fluctuates between $4/3$ and $16/3$ on each interval where $\lfloor \log_2 n \rfloor$ is constant. However when we reach the end of this interval $\lfloor \log_2 n \rfloor$ is off by almost one from the true value, reducing $16/3$ to $4/3$ when the bounds are expressed in $n.$ 
This link points to a series of similar calculations.
A: Suppose that $n>1$, and you knew that $C_k<4k^2$ for every positive integer $k<n$. Let $k=\left\lfloor\frac{n}2\right\rfloor<n$; $0<k<n$, so $C_k<4k^2$. Note that $k\le\frac{n}2$, so $k^2\le\frac{n^2}4$. Thus, 
$$C_n=C_k+n^2<4k^2+n^2\le 4\cdot\frac{n^2}4+n^2=2n^2<4n^2\;.$$
Now we know that $C_k<4k^2$ for every positive integer $k\le n$, not just for every $k<n$. Since we did this without making any special assumptions about $n$ (other than that $n>1$), and since it’s certainly true that $C_1<4\cdot1^2$, we can conclude that $C_k<4k^2$ for all positive integers $k$. If it weren’t, there would be some smallest positive integer $n$ for which it failed. But then it would be true for each $k<n$, and we just showed that in that case it must be true for $n$ as well. Thus, there cannot actually be any $n$ for which it fails.
A: We have
$$
C_1=0<4,\ C_2=C_1+1=1<16.
$$
If we suppose that $C_k<4k^2$ for $k \ge 2$, then:


*

*For $k=2n-1$ we have
$$
C_{k+1}=C_n+4n^2<8n^2=2(k+1)^2<4(k+1)^2;
$$

*For $k=2n$ we have
$$
C_{k+1}=C_n+(2n+1)^2<4n^2+(2n+1)^2=2k^2+2k+1<4(k+1)^2.
$$
