Calculation of sum with many indexes

Question

How to calculated this sum in the closed form?

$$ \sum_{(i_1,i_2,\ldots,i_k)\atop 1\leq i_1<i_2<\ldots<i_k\leq n} 2^{2(i_1+i_2+\ldots+i_k)-k} $$

Here $n$ is positive integer, $1\leq k\leq n$;

$n$ and $k$ are fixed positive integers.

I tried to obtain sums of geometric progressions but the number of these sums of geometric progressions is variable and I cannot calculate this sum.

Answer 1

Let $a_{n,k}$ be the sum.

First method: Show that $a_{n+1,k} = a_{n,k} + 2^{2n+1}a_{n,k-1}$. (Add separately the terms corresponding to $i_k = n+1$ and the terms with $i_k \leq n$.) Use that to prove by induction that $$a_{n,k} = \frac{(2^{2n+1} -2^1)(2^{2n+1}-2^3)\dotsb (2^{2n+1}-2^{2k-1})}{(2^2-1)(2^4-1)\dotsb(2^{2k}-1)}$$

Second method: $a_{n,k}$ is the coefficient of $t^k$ in the polynomial $P(t) = (1+2t)(1+2^3t) \dotsb (1+2^{2n-1}t)$, hence

$$a_{n,k} = \frac{1}{k!}P^{(k)}(0)$$

Use $(1+2t)P(4t) = (1+2^{2n+1}t)P(t)$ so show, by induction on $m$, that $$m(2^{2n+1}P^{(m-1)}(t) - 2^{2m-1}P^{(m-1)}(4t)) = 2^{2m}(1+2t) P^{(m)}(4t) + (1+2^{2n+1}t)P^{(m)}(t)$$

For $t=0$ that yields

$$P^{(m)}(0) = m\frac{2^{2n+1}-2^{2m-1}}{2^{2m}-1} P^{(m-1)}(0)$$

and this allows one to compute $P^{(k)}(0)$, hence $a_{n,k}$.

Comment: $$\sum_{k=1}^n a_{n,k} = P(1) -1 = (1+2)(1+2^3) \dotsb (1+2^{2n-1}) -1$$