Generating function for Minkowski Sum Suppose you have a triangle with vertices $(1,0),(0,1), (0,0)$, and let $P$ be the number of all integer coordinates in the triangle. So $P=3$. Then the Minkowski sum $P+P$ is the set of points found by adding all possible pairs of integer coordinates in the triangle. So $P+P$ consists of points in the original triangle, as well as points $(2,0), (0,2), (1,1)$, and thus $P+P=6$. It was mentioned to me that the generating function for this sequence of sums is given by 
$$
p(x)=\frac{1}{(1-x)^3}
$$
by I don't see why. What is the derivation of this? Thanks.
 A: The third stage $P+P+P$ has the existing points plus (3,0), (2,1), (1,2), (0,3) to give a total of 10 points and it should be obvious that the $n^{\text{th}}$ stage adds $n+1$ additional points thus producing the (offset) triangle numbers at each stage.  You should also be able to see that the starting place or $0^{\text{th}}$ stage is just $(0,0)$ to which you add $P$ to get the first stage, so has 1 point.  So the sequence of numbers of points is $1,3,6,10,\ldots$.  You want this as a generating function, so you want an expression for 
$$g(x) = 1 + 3x + 6x^2 + 10x^3 + \cdots + \frac{(n+1)(n+2)}{2} x^n +  \cdots$$
Some of us can spot such things from familiarity but one way to derive it is to see that
$$ \int \int g(x) \, dx \, dx = A + Bx + x^2 /2 + x^3 /2 + x^4 /2 + x^5/2 + \cdots + x^{n+2} /2 +  \cdots $$
This is essentially a simple geometric series with sum $A+Bx +\frac{x^2}{2(1-x)}$ and then reversing the double integration we find
$$g(x) = \frac{d}{dx}  \frac{d}{dx} \left( A+Bx +\frac{x^2}{2(1-x)} \right) = \frac{1}{(1-x)^3}$$
A: The number of points after adding $n$ of the $P$s is the number of solutions of non-negative solutions of $a + b \leq n$. Imagine the points $0$ to $n$ on a line. Pick two points $p_1<p_2$, and let $a = p_1$, $b = p_2 - p_1 - 1$. This process is reversible, and so the number of solutions is $\binom{n+2}{2}$.
A useful identity is
$$ \sum_{m=0}^n \binom{m + k}{k} = \binom{n+k+1}{k+1}. $$
This is true since each $k+1$ subset of $n+k+1$ with maximal point $M \geq k+1$ is a $k$ subset of $M - 1 \geq k$, and this process is reversible.
Given a generating series, multiplying it by $1/(1-x) = 1 + x + x^2 + \ldots$ is like computing "running sums". So starting with
$$ 1,0,0,0,\ldots, $$
multiplying by $1/(1-x)$ we get
$$ 1,1,1,1,\ldots, $$
multiplying again we get
$$ 1,2,3,4,\ldots, $$
and once again
$$ 1,3,6,10,\ldots. $$
The general term for $1/(1-x)^d$ is $\binom{n+d-1}{d-1} x^n$, as can be easily proven by induction using the identity above.
