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
-
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\;.$