given OGF of some sequence, provide a closed form expression for the sequence.

Question

If we have OGF(Ordinary Generating Function) of $d_{n}$:

$d(x)=\frac{1}{4-2x+x^2}$

How to get a closed form expression for $d_{n}$?

Answer 1

For someone who may need this.

\begin{equation*} \begin{split} d(x) &= (4-2x+x^2)^{-1} \\ &= \frac{1}{(\alpha -x)(\beta -x)}\\ &= \frac{A}{\alpha -x} + \frac{B}{\beta -x} \end{split} \end{equation*} We can determine that : \begin{equation*} A(\beta -x) + B(\alpha -x) = 1 \end{equation*} So, we have: \begin{equation*} A = \frac{1}{\beta - \alpha},\\ B = \frac{1}{\alpha - \beta} \end{equation*} Thus, \begin{equation*} \begin{split} d(x) &= \frac{1}{\beta - \alpha} (\frac{1}{\alpha - x} - \frac{1}{\beta - x})\\ &= \frac{1}{\beta - \alpha} (\frac{1}{\alpha} \frac{1}{1 - \frac{x}{\alpha}} - \frac{1}{\beta} \frac{1}{1 - \frac{x}{\beta}}) \end{split} \end{equation*} Since we know: \begin{equation*} \frac{1}{1-cx} = \sum_{n \geq 0} c^n x^n \end{equation*} So, \begin{equation} [x^n]d(x) = \frac{1}{\beta - \alpha} (\frac{1}{\alpha^{n+1}}- \frac{1}{\beta^{n+1}}) \end{equation} and we can substitute $\alpha$ and $\beta$ as we know: \begin{equation*} \alpha = 1 - \sqrt{3} i , \beta = 1 + \sqrt{3} i \end{equation*} And (2) can be simplified as following: \begin{equation*} \begin{split} [x^n]d(x) &= \frac{1}{\beta - \alpha} (\frac{1}{\alpha^{n+1}}- \frac{1}{\beta^{n+1}})\\ &= \frac{1}{2\sqrt{3}i}(\frac{1}{ (1 - \sqrt{3} i)^{n+1}} - \frac{1}{ (1 + \sqrt{3} i)^{n+1}})\\ &= \frac{1}{2\sqrt{3}i} \frac{ (1 + \sqrt{3} i)^{n+1} - (1 - \sqrt{3} i)^{n+1}}{4^{n+1}} \\ &= \frac{1}{2^{n+2} \sqrt{3}i} [(\frac{1}{2} + \frac{\sqrt{3}}{2}i)^{n+1} - (\frac{1}{2} - \frac{\sqrt{3}}{2}i)^{n+1}] \\ &= \frac{1}{2^{n+2} \sqrt{3}i} [(\cos\frac{\pi}{3} + i\sin \frac{\pi}{3} )^{n+1} - (\cos\frac{-\pi}{3} + i\sin \frac{-\pi}{3} )^{n+1}] \\ &= \frac{1}{2^{n+2} \sqrt{3}i} \{exp[\frac{(n+1)\pi i}{3}] - exp[-\frac{(n+1)\pi i}{3}]\} \\ &= \frac{1}{2^{n+2} \sqrt{3}i} [(\cos\frac{(n+1)\pi}{3} + i\sin \frac{(n+1)\pi}{3} ) - (\cos\frac{-(n+1)\pi}{3} + i\sin \frac{-(n+1)\pi}{3} )]\\ &= \frac{1}{2^{n+2} \sqrt{3}i} [2i\sin\frac{(n+1)\pi}{3}] \\ &= \frac{\sqrt{3}}{3 \cdot 2^{n+1}} \sin[\frac{(n+1)}{3} \pi] \end{split} \end{equation*}