# Lower bound on $c_n = 4c_{\lfloor n/2 \rfloor} + n$

Define a sequence $$c_1,c_2,\dots$$ by the equations $$c_1=0, \quad c_n = 4c_{\lfloor n/2 \rfloor} + n \text{ for all } n > 1.$$ Prove that $$\frac{(n+1)^2}{8} < c_n$$ for all $$n \geq 2$$.

Hint: $$\lfloor \frac{n}{2} \rfloor \geq \frac{n-1}{2}$$ for all $$n$$.

How do I solve this question? I have no idea how to start.

• Use induction. The claim for $n=0$ is $c_0=0>(0+1)^2/8$, which is true. Then assume that $c_{k}>(k+1)^2/8$, for all $k<n$, and use it to show that $c_{n}=4c_{[n/2]}+n>(n+1)^2/8$. We have that $c_n=4c_{[n/2]}+n>4([n/2]+1)^2/8+n$, where the inequality was by using the assumption with $k=[n/2]$. Now use the hint to get that this is larger than $4((n-1)/2+1)^2/8+n=(n+1)^2/8+n>(n+1)^2/8$. – plop Mar 7 at 13:56

Let's start with the case $$n = 2^k$$. We have \begin{align} c_{2^k} &= 2^k + 4c_{2^{k-1}} \\ &= 2^k + 4 \cdot 2^{k-1} + 16c_{2^{k-2}} \\ &= \cdots \\ &= 2^k + 4 \cdot 2^{k-1} + 4^2 \cdot 2^{k-2} + \cdots + 4^{k-1} \cdot 2^1 + 4^k c_1 \\ &= 2^k + 4 \cdot 2^{k-1} + 4^2 \cdot 2^{k-2} + \cdots + 4^{k-1} \cdot 2 = \\ &= 2^k(1 + 2 + 2^2 + \cdots + 2^{k-1}) \\ &= 2^k(2^k-1). \end{align} It is easy to prove by induction that the sequence $$c_n$$ is monotone. Therefore, if $$2^k \leq n < 2^{k+1}$$, $$c_n \geq c_{2^k} = 2^k(2^k-1) > \frac{n}{2}\left(\frac{n}{2}-1\right).$$ Now $$\frac{n}{2}\left(\frac{n}{2}-1\right) \geq \frac{(n+1)^2}{8} \Longleftrightarrow 2n(n-2) \geq (n+1)^2 \Longleftrightarrow n^2 \geq 6n + 1.$$ This holds for all $$n \geq 7$$. You can check that your inequality holds for $$n=2,3,4,5,6$$ directly.
You can also likely prove the inequality directly by induction, but the argument above is more similar to stuff you might actually see later on. The idea is that we find a specific type of $$n$$ for which $$c_n$$ is particular easy to calculate and to compare to $$n$$, and then we try to understand $$c_n$$ for all $$n$$ using these specific values.