How to solve the recurrence relation $a_{1}=2, a_{n}=\frac{a_{n-1}+2}{2 a_{n-1}+1}(n \geq 2)$ with generating functions?

Question

There's already a way to solve it, called "fixed point method", that is, from the relation we define its characteristic equation as $x=\dfrac{x+2}{2x+1}$，then we have $x_1=1,x_2=-1$. So the following relation established: $$ \frac{a_{n}-1}{a_{n}+1}=\frac{\frac{a_{n-1}+2}{2 a_{n-1}+1}-1}{\frac{a_{n-1}+2}{2 a_{n-1}+1}+1}=-\frac{1}{3} \cdot \frac{a_{n-1}-1}{a_{n-1}+1} $$ It is obvious that $\displaystyle \frac{a_{n}-1}{a_{n}+1}=\frac{1}{3} \cdot\left(-\frac{1}{3}\right)^{n-1}$, and then we have $a_{n}=\dfrac{3^{n}-(-1)^{n}}{3^{n}+(-1)^{n}}$.

My question is, how to solve this kind of recurrence relations with generating functions? Also, "fixed points" can be applied to solving recurrences like $a_{n+1}=\dfrac{a_{n}^{2}+b}{2 a_{n}+d}$, which seems impossible to solve using generating functions.

Answer 1

Let $a_0:=0$, and let $$f(x):=\sum_{n=0}^\infty a_nx^n$$ be the generating function of the sequence $(a_n)_{n\geq0}$. Since $\lim_{n\to\infty} a_n=1$ this $f$ is even a bona fide analytic function in the unit disc. We have $$a_n\bigl(1+(-1/3)^n\bigr)=(1-(-1/3)^n\bigr)\qquad(n\geq0)$$ and therefore $$a_n\bigl(x^n+(-x/3)^n\bigr)=\bigl(x^n-(-x/3)^n\bigr)\qquad(n\geq0)\ .$$ This implies $$f(x)+f\left(-{x\over3}\right)={1\over1-x}-{1\over1+{x\over3}}={4x\over(1-x)(3+x)}\qquad\bigl(|x|<1\bigr)$$ and shows that your generating function fulfills a certain functional equation.

I don't know what to make with this.

Answer 2

$\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{\on}[1]{\operatorname{#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}$ $\ds{\bbox[5px,#ffd]{% \left\{\begin{array}{rcl} \ds{a_{1}} & \ds{=} & \ds{2} \\ \ds{a_{n}} & \ds{=} & \ds{{a_{n - 1} + 2 \over 2 a_{n - 1} + 1}\,,\quad n \geq 2} \end{array}\right.}}$

---

$\ds{\large Another\ Method}$: Lets $\ds{a_{n} \equiv x_{n}/y_{n}}$ such that \begin{align} &\bbox[5px,#ffd]{a_{n} = {x_{n} \over y_{n}} = {x_{n - 1}\,/y_{n - 1} + 2 \over 2x_{n - 1}\,/y_{n - 1} + 1} = {x_{n - 1} + 2y_{n - 1} \over 2x_{n - 1} + y_{n - 1}}} \end{align} and sets $\ds{\quad x_{n} = x_{n - 1} + 2y_{n - 1}\,,\quad y_{n} = 2x_{n - 1} + y_{n - 1}}$ which is equivqlent to \begin{align} \pars{\begin{array}{c}\ds{x_{n}} \\ \ds{y_{n}}\end{array}} & = \pars{\begin{array}{cc} \ds{1} & \ds{2} \\ \ds{2} & \ds{1} \end{array}} \pars{\begin{array}{c} \ds{x_{n - 1}} \\ \ds{y_{n - 1}} \end{array}} = \pars{\begin{array}{cc} \ds{1} & \ds{2} \\ \ds{2} & \ds{1} \end{array}}^{2} \pars{\begin{array}{c} \ds{x_{n - 2}} \\ \ds{y_{n - 2}} \end{array}} \\[5mm] & = \cdots = \pars{\begin{array}{cc} \ds{1} & \ds{2} \\ \ds{2} & \ds{1} \end{array}}^{n - 1} \pars{\begin{array}{c} \ds{x_{1}} \\ \ds{y_{1}} \end{array}} \end{align} The above matrix has eigenvalues $\ds{\lambda_{1} = 3}$ and $\ds{\lambda_{2} = -1}$ with, respectively, orthonormal eigenvectors $\ds{{\bf u}_{1} = {1 \over \root{2}}{1 \choose 1}}$ and $\ds{{\bf u}_{2} = {1 \over \root{2}} {-1 \choose \phantom{-}1}}$. Then, \begin{align} \pars{\begin{array}{cc} \ds{1} & \ds{2} \\ \ds{2} & \ds{1} \end{array}} & = \sum_{j = 1}^{2}\lambda_{j}\,{\bf u}_{j}\,{\bf u}_{j}^{T} \\[5mm] \mbox{and}\ \pars{\begin{array}{cc} \ds{1} & \ds{2} \\ \ds{2} & \ds{1} \end{array}}^{n - 1} & = \sum_{j = 1}^{2}\lambda_{j}^{n - 1}\,\, {\bf u}_{j}\,{\bf u}_{j}^{T} \\[2mm] & = { 1 \over 2}\pars{\begin{array}{cc} \ds{3^{n -1} - \pars{-1}^{n}} & \ds{3^{n -1} + \pars{-1}^{n}} \\ \ds{3^{n -1} + \pars{-1}^{n}} & \ds{3^{n -1} - \pars{-1}^{n}} \end{array}} \end{align} Therefore, \begin{align} a_{n} & = {\bracks{3^{n - 1} - \pars{-1}^{n}}\ \overbrace{x_{1}/y_{1}}^{\ds{= a_{1} = 2}}\ +\ 3^{n - 1} + \pars{-1}^{n} \over \bracks{3^{n - 1} + \pars{-1}^{n}}x_{1}/y_{1} + 3^{n - 1} - \pars{-1}^{n}} \\[5mm] & = \bbx{3^{n} - \pars{-1}^{n} \over 3^{n} + \pars{-1}^{n}} \\ & \end{align}