Recurrence relation T(n)=nT(n/2)+n

Question

How to solve the recurrence relation $$T(n)=nT(n/2)+n$$ with initial condition $$T(1)=1$$

I tried to let $$ U(k) = 2^k U(k-1) + 2^k$$ and then $T(n) = U(log(n))$

However, this approach did not yield meaningful results, as I encountered difficulty in solving $U$ due to the presence of a constant term $2^k$.

.

Answer 1

I was able to duplicate your result and here answer the question as to simplifying the result, in particular, the exponents.

From your result in one of the comments

$$ T(k)=2^{(k^2 + k)/2} + \sum_{i=1}^{k} 2^{ik-(i^2 - i)/2} $$

The first exponent can be expressed as $(k^2 + k)/2=\text{binomial}(k+1,2)$. The second required searching in OEIS, entry A141419 (OEIS A141419). This is identified as a triangle read by rows, that is,

$$ ik-(i^2 - i)/2=\text{binomial}(k+1,2)-\text{binomial}(k+1-i,2) $$

With both $k$ and $i$ being vectors, the exponents itself becomes a triangle matrix. The first nine rows are shown below.

$$ \begin{align} &1\\ &2\quad 3\\ &3\quad 5\quad 6\\ &4\quad 7\quad 9\quad 10\\ &5\quad 9\quad 12\quad 14\quad 15\\ &6\quad 11\quad 15\quad 18\quad 20\quad 21\\ &7\quad 13\quad 18\quad 22\quad 25\quad 27\quad 28\\ &8\quad 15\quad 21\quad 26\quad 30\quad 33\quad 35\quad 36\\ &9\quad 17\quad 24\quad 30\quad 35\quad 39\quad 42\quad 44\quad 45\\ &\vdots \end{align} $$

Answer 2

I considered sum $$S_n=2^{1}+2^{1+2}+2^{1+2+3}+\cdots+2^{1+2+3+\cdots+n}=(\sqrt{2})^{1\cdot 2}+(\sqrt{2})^{2\cdot 3}+(\sqrt{2})^{3\cdot 4}+\cdots+(\sqrt{2})^{n\cdot (n+1)}=\\ =\sum\limits_{k=1}^{n}(\sqrt{2})^{k\cdot (k+1)} = \sum\limits_{k=1}^{n}u_k\quad(1)$$ which is sum of, possibly, it can be called "quasi-geometric" progression members, because recurrence connection is $u_{k+1}=2^{k+1}\cdot u_k$ i.e. we have variable ratio.

Very rough estimation for sum gives $$S_n=O\Big(n \cdot (\sqrt{2})^{n\cdot (n+1)}\Big)\quad(2)$$.

I keep trying to simplify $(1)$ (as much as the NY allows), though, imo, Faulhaber's formula gives me hope, that $(2)$ is tight. I would be grateful to anyone who has already seen something similar and can shed more light than I can now.