Power series and recurrence

$\sum_{n=0}^{\infty} a_nz^n$, when $a_0=1,a_1=-1$, and $3a_n+4a_{n-1}-a_{n-2}=0$ for $n>1$.

The recurrence for the coefficients can be solved explicitly by using generating functions. Call $A(z) = \sum_{n \ge 0} a_n z^n$ (coincidentally, just your series). Write the recurrence as $3 a_{n + 2} + 4 a_{n + 1} - a_n = 0$. Using properties of generating functions (see Wilf's "generatingfuctionology" for details): $$3 \frac{A(z) + z - 1}{z^2} + 4 \frac{A(z) + 1}{z} - A(z) = 0$$ This gives: $$A(z) = \frac{7 z - 3}{z^2 - 4 z - 3}$$ The radius of convergence is given by the absolute value of the root of $z^2 - 4 z - 3$ nearest to the origin, which gives a radius of convergence of $\sqrt{7} - 2$.

• Nice solution :) – Hanul Jeon Jan 22 '13 at 16:41

The recurrence relation is constant coefficient, lending itself to a relatively simple solution: if we assume that $a_n = A r^n$, then $r$ satisfies $3 r^2 + 4 r - 1=0$, with solution $r = (-2 \pm \sqrt{7})/3$. The solution to the recurrence is

$$a_n = A \left (\frac{\sqrt{7} - 2}{3} \right )^n + B (-1)^n \left (\frac{\sqrt{7} + 2}{3} \right)^n$$

You may then evaluate the sum analytically as a geometric series:

$$\sum_{n=0}^{\infty} a_n z^n = A \frac{3}{3-(\sqrt{7} - 2) z} + B \frac{3}{3+(\sqrt{7} + 2) z}$$

The radius of convergence is dictated by the pole closest to the origin, which would then give

$$|z| \le R = \frac{3}{\sqrt{7} + 2} = \sqrt{7} - 2$$

Such a linear recurrence has basic solutions of the form $a_n=\lambda^n$ where $\lambda$ is a solution of $3\lambda^2+4\lambda-1=0$, i.e. we have $\lambda=\frac{-2\pm\sqrt 7}3$. The genereal solution has the form $$a_n=\alpha\left(\frac{-2+\sqrt 7}3\right)^n+\beta \left(\frac{-2-\sqrt 7}3\right)^n$$ where $\alpha,\beta$ can be determined from the two startuing values $a_0, a_1$. Suffice it to say that neither $\alpha$ nor $\beta$ is $0$. Then $$\limsup_{n\to\infty}\sqrt[n]{|a_n|}=\max\left\{\left|\frac{-2+\sqrt 7}3\right|,\left|\frac{-2-\sqrt 7}3\right|\right\}$$ and the reciprocal of this is the radius of convergence.