How is $\sum_{i=0}^{\infty}\sum_{j=0}^{\infty}x^{i+j} = \sum_{n=0}^{\infty}\sum_{i=0}^{n}x^n$

Question

My professor used this in class for a proof and I'm having trouble understanding it.

$\sum_{i=0}^{\infty}\sum_{j=0}^{\infty}x^{i+j} = \sum_{n=0}^{\infty}\sum_{i=0}^{n}x^n$

The way he explained it, you are reindexing the first summation using $n = i+j$, so $ 0 \leq i \leq n$ and then $j = n-i$, but this makes even less sense to me.

So my question is, what is going on here? How is this true? I'm totally lost.

(I have confirmed that this is true though https://www.wolframalpha.com/input/?i=sum+(+sum+(x%5En),+i+%3D+0+to+n),+n+%3D+0+to+infinity+%3D%3D%3D+sum+(+sum+(x%5E(i%2Bj)),+j+%3D+0+to+infinity),+i+%3D+0+to+infinity

Answer 1

In the double sum $$\sum_{i=0}^{\infty}\sum_{j=0}^{\infty}x^{i+j}$$ $x^n$ appears when $(i,j) \in \{ (0,n), (1,n-1),..., (n,0)\}$, meaning $n+1$ times. Therefore $$\sum_{i=0}^{\infty}\sum_{j=0}^{\infty}x^{i+j} = \sum_{n=0}^{\infty}(n+1)x^n$$

Now, $$(n+1)x^n = \sum_{i=0}^{n}x^n$$

Answer 2

Think about writing it down in a matrix.

\begin{bmatrix} x^0 & x^1 & x^2 & x^3 \dots \\ 0 & x^1 & x^2 & x^3 \dots \\ 0 & 0 & x^2 & x^3 \dots \\ 0 & 0 & 0 & x^3 \dots \\ \vdots & \vdots & \vdots & \vdots & \ddots & \\ \end{bmatrix}

The first way of writing it is collecting first by rows and then by columns, and the second way is collecting first by columns, then by rows.