Creating a generating function of recurrence sequence

Question

I do not quite understand how to create a generating function of this recurrently given sequence:

$a_0 = 1$,

$a_n = \dfrac{a_{n-1} + a_{n-2}}{2}$ for $n \ge 2$.

$\lim_{n\to \infty} a_n = 0$

If I knew the $a_1$ I think I would be able to create the generating function. I would say

$a_n \cdot x^n = \dfrac{(a_{n-1} + a_{n-2}) \cdot x^n}{2}$

and then make sums of it and continue. But I am unsure what to do now.

Any help appreciated.

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}$

Define the Generating Function $\ds{\mc{A}\pars{z} \equiv \sum_{n = 0}^{\infty}a_{n}z^{n}}$ such that $\ds{a_{n} = \bracks{z^{n}}\mc{A}\pars{z}}$.

Then, \begin{align} \mc{A}\pars{z} & \equiv \sum_{n = 0}^{\infty}a_{n}z^{n} = a_{0} + a_{1}z + \sum_{n = 2}^{\infty}{a_{n - 1} + a_{n - 2} \over 2}\,z^{n} = 1 + a_{1}z + {1 \over 2}\sum_{n = 1}^{\infty}a_{n}\,z^{n + 1} + {1 \over 2}\sum_{n = 0}^{\infty}a_{n}\,z^{n + 2} \\[5mm] & = 1 + a_{1}z - {1 \over 2}\,a_{0}z + {1 \over 2}\,z\sum_{n = 0}^{\infty}a_{n}\,z^{n} + {1 \over 2}\,z^{2}\sum_{n = 0}^{\infty}a_{n}\,z^{n} \\[5mm] & = 1 + \pars{a_{1} - {1 \over 2}}z + {1 \over 2}\,z\,\mc{A}\pars{z} + {1 \over 2}\,z^{2}\mc{A}\pars{z} \implies \bbx{\mc{A}\pars{z} = {1 + \pars{a_{1} - 1/2}z \over 1 - z/2 - z^{2}/2}} \end{align}

---

\begin{align} \mc{A}\pars{z} & = -\,{\pars{2a_{1} - 1}z + 2 \over z^{2} + z - 2} = -\,{1 \over 3}\,{2a_{1} + 1 \over z - 1} - {4 \over 3}\,{a_{1} - 1 \over z + 2} \\[5mm] & = {1 \over 3}\,\pars{2a_{1} + 1}\sum_{n = 0}^{\infty}z^{n} - {2 \over 3}\,\pars{a_{1} - 1} \sum_{n = 0}^{\infty}{\pars{-1}^{n} \over 2^{n}}z^{n} \\[5mm] & = \sum_{n = 0}^{\infty}\bracks{{1 \over 3}\pars{2a_{1} + 1} - {2 \over 3}\,\pars{a_{1} - 1}{\pars{-1}^{n} \over 2^{n}}}z^{n} \end{align}

The condition $\ds{\lim_{n \to \infty}a_{n} = 0}$ is satisfied whenever $\ds{a_{1} = -\,{1 \over 2}}$.

Then, $$ \bbx{a_{0} = 1\,,\quad a_{1} = -\,{1 \over 2}\,, \qquad a_{n} = {\pars{-1}^{n} \over 2^{n}}\quad\mbox{when}\quad n \geq 2} $$