What is this sum $\sum_{i=0}^{n-1}\sum_{j=0}^{i}x^i$?

Question

How to find this sum ? $$\sum_{i=0}^{n-1}\sum_{j=0}^{i}x^i$$ without knowing this sum: $$\sum_{i=1}^{n}ix^{i-1} = \frac{nx^{n+1}-(n+1)x^n+1}{(x-1)^2}$$

Answer 1

A variation based upon changing the order of summation.

We obtain \begin{align*} \color{blue}{\sum_{i=0}^{n-1}\sum_{j=0}^ix^i}&=\sum_{\color{blue}{0\leq j\leq i\leq n-1}}x^i=\sum_{j=0}^{n-1}\sum_{i=j}^{n-1}x^{i}\tag{1}\\ &=\sum_{j=0}^{n-1}\sum_{i=0}^{n-1-j}x^{i+j}\tag{2}\\ &=\sum_{j=0}^{n-1}x^j\frac{1-x^{n-j}}{1-x}\tag{3}\\ &=\frac{1}{1-x}\sum_{j=0}^{n-1}x^j-\frac{x^n}{1-x}\sum_{j=0}^{n-1}1\tag{4}\\ &=\frac{1-x^n}{(1-x)^2}-\frac{nx^n}{1-x}\tag{5}\\ &\,\,\color{blue}{=\frac{nx^{n+1}-(n+1)x^n+1}{(1-x)^2}} \end{align*}

Comment:

• In (1) we change the order of summation.

• In (2) we shift the index to start with $i=0$.

• In (3) we factor out $x^j$ and apply the geometric series formula.

• In (4) we multiply out.

• In (5) we apply the geometric series formula again.

Answer 2

You have $$\sum_{i=1}^{n}ix^{i+1}=\sum_{i=0}^{n-1}(i+1)x^i$$ $$=\sum_{i=1}^{n-1} \underbrace{(1+1+...+1)}_{i+1\text{ times}}x^{i}$$ $$=\sum_{i=1}^{n-1}\sum_{j=0}^{i}x^i.$$

It is a geometric series so we have $$\sum_{i=0}^{n}x^{i}=\frac{1-x^{n+1}}{1-x}$$

Thus $\sum_{i=1}^{n}ix^{i-1}=\frac{d}{dx}\big(\frac{x^{n+1}-1}{x-1}\big)=\frac{nx^{n+1}-(n+1)x^n+1}{(x-1)^2}$ which is valid for $x\neq 1$.

If you didn't have this sum then $$S=\sum_{i=1}^{n}ix^{i-1}=1+2x+3x^2+4x^3+...+(n-1)x^{n-2}+nx^{n-1}$$ $$x^2S=x^2+2x^3+3x^4+4x^5+...+(n-2)x^{n-1}+(n-1)x^{n}+nx^{n+1}$$ $$-2xS=-2x-4x^2-6x^3-8x^4-...-2(n-1)x^{n-1}-2nx^{n}$$

Now adding the above you have $$S(x^2-2x+1)=1+nx^{n+1}+(n-1)x^n-2nx^n=nx^{n+1}-(n+1)x^n+1$$

Thus $$S=\frac{nx^{n+1}-(n+1)x^n+1}{(x-1)^2}$$

Answer 3

Hint:

This sum is \begin{align} \sum_{i=0}^{n-1}\sum_{j=0}^{i}x^i&=\sum_{i=0}^{n-1}(i+1)x^i=\sum_{i=0}^{n-1}(x^{i+1})'\\ &=\biggl(\sum_{i=1}^{n} x^{i}\biggr)'=\dotsm \end{align}

Answer 4

After some simplifications, you have,

$$ \sum_{i=0}^{n-1} (i+1)x^i= Q$$

Now consider,

$$ \sum_{i=0}^{n-1} x^i = \frac{x^n-1}{x-1}$$

Differentiate both sides

$$ \sum_{i=0}^{n-1} i x^{i-1} = ( \frac{x^n -1}{x-1})'$$

Now, multiply both sides by $x$

$$ \sum_{i=0}^{n-1} i x^i = x( \frac{x^n -1}{x-1})'$$

Add this to the firstly considered expression:

$$ \sum_{i=0}^{n-1} i x^i + \sum_{i=0}^n x^i = x( \frac{x^n-1}{x-1})' + \frac{x^n -1}{x-1}$$

or,

$$ \sum_{i=0}^{n-1} (i+1) x^i = x( \frac{x^n-1}{x-1})' + \frac{x^n -1}{x-1}$$

---

Note, I used the theorem that we can interchange sum, i.e: sum of derivatives = derivative of the total sum.

$$ \frac{d}{dx} \sum = \sum \frac{d}{dx}$$