Closed Formula For $\sum_{i =1}^{n}(n-i)\cdot 2^{i-1}$

Question

I had tried to find the closed formula for $$\sum_{i =1}^{n}(n-i)\cdot 2^{i-1}$$ combinatorially following algorithm:

$$\sum_{i =1}^{n}(n-i)\cdot 2^{i-1} =\frac{1}{2}\sum_{i =1}^{n}(n-i)\cdot 2^{i}. $$

$1.$ $2^i$ represent total number of subset of $[i]$.

$2.$ $(n-i)$ represent the whole possible cases of choosing one elment among $[n-i]$

Considering the $1.$ and $2$. same time, $1/2\cdot\sum_{i =1}^{n}(n-i)\cdot 2^{i} $ represents among ordered $n$ elements $1,2,3,4...,n$, choose fist $i$ element and put them into a set. Then among the rest of them choose another one to put it into the same set. Then multiply $1/2$ which reduces the duplicated counting to represent "total number of subsets of [n] which contains at least one element in it"

Therefore, the answer is $2^{n-1}-1$.

Is this algorithm logically clear?

---

add: Reference to comments, the answer is $2^n - n - 1$ which corresponds to the number of total subset with size more than 2

How could one relate this fact to the given summation?

Answer 1

Let $f(x)=x+x^2+...+x^n$.

Thus, $$f'x)=1+2x+...+nx^{n-1}=\left(\frac{x(x^n-1)}{x-1}\right)'=\frac{((n+1)x^n-1)(x-1)-(x^{n+1}-x)}{(x-1)^2}.$$ Hence, $$1+2\cdot2+3\cdot2^2+...+n2^{n-1}=(n+1)\cdot2^n-1-2^{n+1}+2=(n-1)2^n+1.$$ Id est, $$\sum\limits_{i=1}^n(n-i)2^{i-1}=n\cdot\frac{2^n-1}{2-1}-(n-1)2^n-1=$$ $$=n(2^n-1)-(n-1)2^n-1=2^n-n-1.$$

Answer 2

Let $n-i=k$$$$$ $$S=\frac{1}{2} \sum_{k=0}^{n-1} k\cdot 2^{n-k}$$$$$$ $$2S= \sum_{k=0}^{n-1} k\cdot 2^{n-k}$$$$$$

$$2S= 2^{n-1} + 2× 2^{n-2} + 3× 2^{n-3}+\cdots +(n-2) ×2^2 +(n-1)× 2$$$$$$ Dividing both sides by 2, $$S=2^{n-2} +2 ×2^{n-3} +3 ×2^{n-4} +\cdots + (n-2)× 2 + (n-1)$$ $$$$

Now $2S -S$ gives us$$$$ $$S=2^{n-1} +2^{n-2}+2^{n-3}+\cdots +2^2+2-(n-1)$$$$$$ Using GM formula, $$S=2 \frac{2^{n-1}-1}{2-1} -(n-1)$$$$$$ $$S=2^{n} -2 -n +1$$$$$$ $$S= 2^n-(n+1)$$$$$$

Answer 3

As you say in your answer, $$2^n-(n+1)=|X=\{A\subseteq [n]:|A|>2\}|,$$ where $[n]=\{1,2,\cdots , n\}.$ Now, consider the following sets $$A_i = \{A\subseteq[n]:i\in A,\exists ! j\in A\text{ s.t } i<j\}.$$ So, for choosing $j$ we have $(n-i)$ possibilities because those are the numbers greater than $i.$ Also, perhaps $A$ contains elements less than $i,$ so to choose them we can do it in $2^{i-i}$ ways, so $$|A_i| = (n-i)2^{i-1},$$ now check that the $A_i$ are pairwise disjoint and use the sum principle.