Find a formula for the recurrence relation $x(n) = x(\lfloor n/2 \rfloor) + n\,a\,x(1) = 1$

Question

Do you know how to find a formula for a sequence below? $$\begin{align*} x(n) &= x(\lfloor n/2 \rfloor) + n\\ x(1) &= 1 \end{align*}$$

What is $x(2^k)$? What is $x(n)$ when $2^k \leq n < 2^{k+1}$?

Answer 1

You really need to start showing at least a little effort to solve these questions. I’ll give you a sort of road map for this one, but I’ll leave a great deal of the work for you.

At a bare minimum you could take the obvious first step towards answering the first question: gather some data. Don’t be afraid to do some numerical experimentation: that’s how you start to get a sense of what’s going on, and it’s something that you should do especially whenever — as here — it appears that you’re being asked to spot and prove some sort of numerical pattern or formula. Here we easily get the following data:

$$\begin{array}{rcc} k:&0&1&2&3&4&5\\ 2^k:&1&2&4&8&16&32\\ x(2^k):&1&3&7&15&31&63 \end{array}$$

From this you should be able quite easily to guess a closed form for $x(2^k)$ in terms of $k$, and you can then prove it by induction on $k$.

The second question is significantly harder, but here again you should begin by gathering the data in the first two columns of the table below.

$$\begin{array}{c|c} n&x(n)&?\\ \hline 1&1\\ \hline 2&3\\ 3&4&3+1\\ \hline 4&7\\ 5&8&7+1\\ 6&10&7+3\\ 7&11&7+4\\ \hline 8&15\\ 9&16&15+1\\ 10&18&15+3\\ 11&19&15+4\\ 12&22&15+7\\ 13&23&15+8\\ 14&25&15+10\\ 15&26&15+11\\ \hline 16&31 \end{array}$$

The third column is not necessarily something that you’d think to try right away. However, the form of the question suggests dividing the table into blocks as I did, and looking at how the numbers grow in each block is one of the more natural things to do.

Study that table for a while, extending it for another block or two if necessary, until you can fill in the following

Conjecture: If $n=2^k+\ell$, where $0<\ell<2^k$, then $x(n)=x(2^k)+x(?)$.

If you have the right conjecture, it can also be proved by induction on $k$.

One has to go a bit further to get a closed form for $x(n)$, and I can’t tell whether you’re actually supposed to do so. If you are, I suggest that you write $n$ in binary (base two):

$$n=(b_kb_{k-1}\ldots b_1b_0)_{\text{two}}=\sum_{i=0}^kb_i2^i\;,$$

where each $b_i$ is $0$ or $1$. If you then apply the conjecture above and what you know about $x(2^i)$, you’ll find that $x(n)$ can be expressed quite nicely in terms of $n$ and the binary digits $b_0,\ldots,b_k$.