Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Prove that

$ f(n) = n - 1 + f(\lfloor {n/2} \rfloor) + f(\lceil n/2 \rceil)$ where $f(n) = \sum_1^n{\lceil{\log_2 k}\rceil}$

My trials:

At first I find a formula for $f(n)$. If $n = 2^m$ , then in the sum of $f(n) = \sum_1^n{\lceil{\log_2 k}\rceil}$ ,

$m$ appears $2^{m-1}$ times, $m-1$ appears $2^{m-2}$ times,... and so on, till $0$ appearing $1$ time, which gives $f(n) = \sum_1^m{j\cdot 2^{j-1}} = 2^m(m-1) + 1 $.

I want to show the given equation is true for values of $n = 2^m$ only at the moment. Upto this point I could do, but the proof of the given equation is getting a bit too hard for me.

Plugging in the value of $f(2n) = 2^{m+1}\cdot m + 1$ and calculating $2f(n) + n - 1 = 2^m (2m-1) + 1$ is not equalling. * <- OK its equalling, it should be $2f(n) + 2n - 1 = 2^m (2m-1) + 1$ in the second equation.

Instead, I would like to ask for a simpler proof of this identity using the identities $\lceil \log_2 2j \rceil$ = $\lceil \log_2 j \rceil + 1$ and $\lceil \log_2{(2j-1)}\rceil = \lceil \log_2 j \rceil + [j > 1]$, for $j>= 1$ because that's what the book really wants.

Note: this is problem 3.34 of Concrete Math. The hint uses finite calculus, but it also says it can be directly done using simpler logarithmic identities.

share|improve this question
    
You mean $f(n) = \sum_{k=1}^n \lceil \log_2(k) \rceil$ –  Robert Israel Oct 29 '12 at 3:45
    
Oops, thanks I edited it. –  Andariel Oct 29 '12 at 3:54
add comment

2 Answers

up vote 1 down vote accepted

As is fairly standard, I’ll write $\lg n$ for $\log_2 n$. If $f(n)=\sum_{k=1}^n\lceil\lg k\rceil$, we want to show that

$$f(n)=n-1+f\left(\left\lfloor\frac{n}2\right\rfloor\right)+f\left(\left\lceil\frac{n}2\right\rceil\right)\;.\tag{1}$$

The suggestion in the answer at the back of the book is to use the identities

$$\lceil\lg 2j\rceil=\lceil\lg j\rceil+1\tag{2}$$ and $$\lceil\lg(2j-1)\rceil=\lceil\lg j\rceil+[j>1]\tag{3}$$ for $j\ge 1$.

To prove $(2)$, let $k=\lceil\lg j\rceil$. Then $k-1<\lg j\le k$, so $2^{k-1}<j\le 2^k$, and $2^k<2j\le 2^{k+1}$. But then $k<\lg 2j\le k+1$, so $\lceil\lg 2j\rceil=k+1=\lceil j\rceil+1$.

To prove $(3)$, note first that if $j=1$, $\lceil\lg(2j-1)\rceil=0=\lceil\lg j\rceil+0=\lceil\lg j\rceil+[j>1]$. Now assume that $j>1$, and again let $k=\lceil\lg j\rceil$, so that $2^k<2j\le 2^{k+1}$ and hence $2^k-1<2j-1\le 2^{k+1}-1$. Since everything here is an integer, this can be rewritten $2^k\le 2j-1<2^{k+1}$. Moreover, since $j>1$, $2j-1\ge 3$, and therefore $k\ge 1$. Thus, $2^k$ is even and $2j-1$ is odd, so they cannot be equal, and we must actually have $2^k<2j-1<2^{k+1}$. Thus, $k<\lg(2j-1)<k+1$, and $$\lceil\lg(2j-1)\rceil=k+1=\lceil\lg j\rceil+[j>1]\;,$$ completing the proof of $(3)$.

Now return to $(1)$. If $n=2m$ is even,

$$\begin{align*} f(n)&=\sum_{k=1}^{2m}\lceil\lg k\rceil=\sum_{k=1}^m\Big(\lceil\lg 2k\rceil+\lceil\lg(2k-1)\rceil\Big)\\ &=\sum_{k=1}^m\Big(\lceil\lg k\rceil+1\Big)+\sum_{k=1}^m\Big(\lceil\lg k\rceil+[k>1]\Big)\\ &=2\sum_{k=1}^m\lceil\lg k\rceil+2m-1\\ &=n-1+2f(m)\\ &=n-1+f\left(\left\lfloor\frac{n}2\right\rfloor\right)+f\left(\left\lceil\frac{n}2\right\rceil\right)\;. \end{align*}$$

The calculation for the case $n=2m-1$ is similar; I’ll leave it to you to try.

share|improve this answer
    
Thanks, I love your solution and I shall accept it. –  Andariel Oct 29 '12 at 4:54
    
@Andariel: You’re welcome; glad it was helpful. –  Brian M. Scott Oct 29 '12 at 4:57
add comment

Let $R(n) = n-1 + f(\lfloor n/2 \rfloor) + f(\lceil n/2 \rceil)$. Note that $f(1) = 0 = R(1)$. I claim that $f(n+1) - f(n) = R(n+1) - R(n)$, so by induction we will have $f(n)=R(n)$ for all positive integers $n$.

$$\eqalign{f(n+1) - f(n) &= \lceil \log_2(n+1) \rceil\cr R(n+1) - R(n) &= 1 + f(\lfloor (n+1)/2 \rfloor ) - f(\lfloor n/2 \rfloor) + f(\lceil (n+1)/2 \rceil ) - f(\lceil n/2 \rceil)\cr}$$ Case 1: $n = 2j$ is even, $\lfloor n/2 \rfloor = \lceil n/2 \rceil = \lfloor(n+1)/2\rfloor =j$, $\lceil (n+1)/2 \rceil = j+1$, so $$R(n+1) - R(n) = 1 + f(j+1) - f(j) = 1 + \lceil \log_2(j+1) \rceil$$

Case 2: $n=2j+1$ is odd, $\lfloor n/2 \rfloor = j$, $\lceil n/2 \rceil = \lfloor (n+1)/2 \rfloor = \lceil (n+1)/2 \rceil = j+1$, and again

$$R(n+1) - R(n) = 1 + f(j+1) - f(j) = 1 + \lceil \log_2(j+1) \rceil$$

If $2^m < j+1 \le 2^{m+1}$ for integer $m$ so that $\lceil \log_2(j+1)\rceil = m$, then $2^{m+1} < 2j+2 \le 2^{m+2}$. In the first case, since $2j+1$ is odd while $2^{m+1}$ is even we also have $2^{m+1} < 2j+1 = n+1 \le 2^{m+2}$, so $\lceil \log_2(n+1) \rceil = m+2$. In the second case, $n+1=2j+2$ so again $\lceil \log_2(n+1) \rceil = m+2$. Thus in either case $\lceil \log_2(n+1) \rceil = 1 + \lceil \log_2(j+1) \rceil$, i.e. $f(n+1) - f(n) = R(n+1) - R(n)$.

share|improve this answer
    
Thanks, I totally get the idea and the technique you used. One thing is that if $2^m<j+1<= 2^{m+1}$ then $\lceil log_2{(j+1)}\rceil$ would be $m+1$, right? –  Andariel Oct 29 '12 at 4:45
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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