# Proof about some recursion

Let $f(n)=\overset{n}{\underset{k=1}{\Sigma}}\lceil log_{2}k\rceil$. Prove that $$f(n)=n-1+f(\lceil\frac{n}{2}\rceil)+f(\lfloor\frac{n}{2}\rfloor)$$ for all $n\geq1$.

Hint i've got for this: divide $\overset{n}{\underset{k=1}{\Sigma}}\lceil log_{2}k\rceil$ for sums for odd and even $k$'s.

I have tried induction for this, but I can't hit on an idea how to use assumption there since I see only sums.

Thank you in advance for any hints for that.

## 1 Answer

Let's use the hint, if $k$ is even, say $k = 2\kappa$, then $$\def\fl#1{\left\lfloor #1\right\rfloor}\def\cl#1{\left\lceil#1\right\rceil} \cl{\log_2 k} = \cl{\log_2 2\kappa} = \cl{1 + \log_2\kappa} = 1 +\cl{\log_2 \kappa}$$ For odd $k$, say $k = 2\kappa - 1$, we get for $\kappa \ge 2$ noting that 1 is the only odd power of 2, that is, $\log_2 (2\kappa - 1)$ is never an integer for $\kappa \ge 2$, hence $$\cl{\log_2 k} = \cl{\log_2 (2\kappa - 1)} = \cl{\log 2\kappa} = 1 + \cl{\log_2 \kappa}$$ Now consider the cases $n$ odd or even.

• I do not know what does it change for me. It basically means that $f(n)=n\cdot\overset{n}{\underset{k=1}{\Sigma}}\lceil\log_{2}\frac{k}{2}\rceil$, but I can easily hit that conclusion even without your hint, so you meant something else. Can you explain it? (i am still trying to use induction for this, with your hint, but I have no idea). I see that n being odd or even has impact on ceil / floor over function argument but since I just started my discrete mathematics course, knowing what to do now got on top of me a bit. – Annisar Oct 25 '13 at 18:38