Let $$g(x) = \sum_{n = 0}^{\infty} d_n x^n$$ be a generating series for $d_n$, where $d_n$ is the number of integer points in the convex hull of $$(0, 0),(n, 0), (n, n), (0,n)$$ Find a generating function for $d_n$
Generating function
-
2Do you really mean the convex hull of $(n,0), (0,n), (n,0), (0,n)$? Because that is simply the line between the two points $(n,0)$ and $(0,n)$. – 2012-02-29
-
0no, thank you for noticing it! – 2012-03-01
2 Answers
I’m going to guess that you meant the convex hull of $\langle 0,0\rangle,\langle 0,n\rangle,\langle n,0\rangle$, and $\langle n,n\rangle$; if you meant something else, you should still be able to use some of the same ideas.
Since the convex hull in question is a square with $n+1$ integer points on each side, $d_n=(n+1)^2$, and you want $$g(x)=\sum_{n\ge 0}(n+1)^2x^n\;.$$
What if it were only $$f(x)=\sum_{n\ge 0}(n+1)x^n\;?$$ (This, by the way, would be the function that you want for the problem that you actually wrote down.) Then $$f(x)=1+2x+3x^2+4x^3+\dots\;,$$ and it should almost leap out at you that this is the derivative of $$C+x+x^2+x^3+x^4+\dots\tag{1}$$ for any constant $C$. If we take $C=1$, $(1)$ is simply $$\sum_{n\ge 0}x^n\;,$$ and we know that $$\frac1{1-x}=\sum_{n\ge 0}x^n\;.$$ Thus, $$f(x)=D\left(\frac1{1-x}\right)=\frac1{(1-x)^2}\;.$$
Okay, so $$\frac1{(1-x)^2}=\sum_{n\ge 0}(n+1)x^n\;;\tag{2}$$ we want a second factor of $n+1$ in the coefficient. If the exponent in $(n+1)x^n$ were $n+1$, another differentiation would do the trick: differentiating $(n+1)x^{n+1}$ yields $(n+1)^2x^n$. Fortunately, it’s easy enough to boost the exponent from $x^n$ to $x^{n+1}$: just multiply both sides of $(2)$ by $x$ to get
$$\frac{x}{(1-x)^2}=\sum_{n\ge 0}(n+1)x^{n+1}\;.\tag{3}$$
Now just differentiate $(3)$, and you’ll have your function $g(x)$, since the righthand side will become $$\sum_{n\ge 0}(n+1)^2x^n\;.$$