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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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