0
$\begingroup$

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.

2 Answers 2

2

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}, 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), 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.

1

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)$.

  • 0
    Thanks, I totally get the idea and the technique you used. One thing is that if 2^m then $\lceil log_2{(j+1)}\rceil$ would be $m+1$, right?2012-10-29