Easy way to sum this expression $\sum_{n=1}^{10}(n-1)*2^n+1$

Question

So I am doing the AIME $2009$ past papers, and I encountered Problem $8$.

Let $S = \{2^0,2^1,2^2,\ldots,2^{10}\}$. Consider all possible positive differences of pairs of elements of $S$. Let $N$ be the sum of all of these differences. Find the remainder when $N$ is divided by $1000$.

The answer seemed quite straightforward. Just sum the expression $2^n-2^m$ for all possible $(n,m)$ in which $10\geq n>m\geq0$

I organised it a little bit, and got that the sum is equivalent to:

$\sum_{n=1}^{10}(n-1)*2^n+1$

I notice sums like these, with things like $(n-1)k^n$ in the summation are quite common in competition math and number theory. But there doesn't seem to be a simple way to solve them in my knowledge. I could divide them into $9$ different geometric sequences from $2^{x_1}$ to $2^{10}$, starting at $x_1 = 2$. But I wonder if a simpler solution exists.

Answer 1

We can turn this into a power series to make our lives easier. Setting $x=2$ we get the expression

$$x^2\sum_{n=0}^{9}nx^{n-1} + 1 = x^2\left(\sum_{n=0}^9 x^n\right)' + 1 = x^2\left(\frac{x^{10}-1}{x-1}\right)' + 1$$

$$ = \frac{8x^{12}-9x^{11}+x^2+(x-1)^2}{(x-1)^2} \to 7\cdot2^{11}+5$$

Answer 2

Because the AIME does not assume or require a knowledge of calculus, such a sum should be amenable to more elementary methods. As such, consider $$f_n(z) = \sum_{k=0}^n k z^k.$$ Then $$\begin{align*} f_{n+1}(z) - zf_n(z) &= \sum_{k=0}^{n+1} kz^k - \sum_{k=0}^n kz^{k+1} \\ &= \sum_{k=1}^{n+1} kz^k - \sum_{k=0}^n kz^{k+1} \\ &= \sum_{k=0}^n (k+1)z^{k+1} - \sum_{k=0}^n kz^{k+1} \\ &= \sum_{k=0}^n ((k+1) - k)z^{k+1} \\ &= \sum_{k=0}^n z^{k+1} \\ &= \frac{z(z^{n+1} - 1)}{z-1}. \end{align*}$$ But since $f_{n+1}(z) = f_n(z) + (n+1)z^{n+1}$, we have $$(1 - z) f_n(z) = \frac{z(z^{n+1}-1)}{z-1} - (n+1)z^{n+1}$$ therefore $$f_n(z) = \frac{(n+1)z^{n+1}}{z-1} - \frac{z(z^{n+1}-1)}{(z-1)^2}.$$ This formula can then be used to evaluate the desired sum.