Finding generating function for $ h_{n} = h_{n-1} + \binom{n+1}{3} + n$

Question

Let $h_{n}$ denote the number of regions into which a convex polygonal region with $n + 2$ sides is divided by its diagonals, assuming no three diagonals have a common point. With this is the initial condition $h_{0} = 0$.

$$ h_{n} = h_{n-1} + \binom{n+1}{3} + n$$, with $(n \ge 1)$

How does one find the generating function and obtain a formula for $h_{n}$?.

The hardest thing for me is the $\binom{n+1}{3}$ term. I tried expanding it:

$$\binom{n+1}{3} = \frac{(n+1)!}{3!(n+1-3)!} = \frac{n(n+1)(n-1)(n-2)!}{6 (n-2)!} = \frac{n(n+1)(n-1)}{6}$$

And that led to nowhere...Please help!

Answer 1

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

With $\ds{\verts{z} < 1}$:

\begin{align} \sum_{n = 1}^{\infty}h_{n}z^{n} & = \sum_{n = 1}^{\infty}h_{n - 1}\,z^{n} + \sum_{n = 1}^{\infty}{n + 1 \choose 3}z^{n} + \sum_{n = 1}^{\infty}nz^{n} \\[5mm] \implies -h_{0}\ +\ \underbrace{\sum_{n = 0}^{\infty}h_{n}z^{n}}_{\ds{\equiv\ \mc{H}\pars{z}}} & = \sum_{n = 0}^{\infty}h_{n}\,z^{n + 1} + \sum_{n = 0}^{\infty}{n + 2 \choose 3}z^{n + 1} + z\,\totald{}{z}\underbrace{\sum_{n = 1}^{\infty}z^{n}} _{\ds{z \over 1 - z}} \\[5mm] \implies -h_{0} + \mc{H}\pars{z} & = z\,\mc{H}\pars{z} + z\sum_{n = 0}^{\infty}{n + 2 \choose 3}z^{n} + {z \over \pars{1 - z}^{2}} \\[5mm] \implies \mc{H}\pars{z} & = {h_{0} \over 1 - z} + {z \over 1 - z}\sum_{n = 0}^{\infty}{n + 2 \choose 3}z^{n} + {z \over \pars{1 - z}^{3}} \end{align}

Note that

\begin{align} &\bbox[10px,#ffd]{\sum_{n = 0}^{\infty}{n + 2 \choose 3}z^{n}} = \sum_{n = 0}^{\infty}{n + 2 \choose n - 1}z^{n} = \sum_{n = 0}^{\infty}{-4 \choose n - 1}\pars{-1}^{n - 1}z^{n} \\[5mm]= &\ \sum_{n = 0}^{\infty}{-4 \choose n}\pars{-1}^{n}z^{n + 1} = z\sum_{n = 0}^{\infty}{-4 \choose n}\pars{-z}^{n} = z\pars{1 - z}^{-4} \end{align}

---

Then, $$ \bbx{\mc{H}\pars{z} = {h_{0} \over 1 - z} + {z^{2} \over \pars{1 - z}^{5}} + {z \over \pars{1 - z}^{3}}} $$

Answer 2

Hint: $$ \left( x^{n+1} \right)''' = (n+1)\,n\,(n-1)\;x^{n-2} $$