# Generating function for Pell numbers

Problem: The Pell numbers $p_n$ are defined by the recurrence relation \begin{align*} p_{n+1} = 2p_n + p_{n-1} \end{align*} for $n \geq 1$. The initial conditions are $p_0 = 0$ and $p_1 = 1$.

a) Determine the generating function \begin{align*} P(x) = \sum_{n=0}^{\infty} p_n x_n \end{align*} for the Pell numbers. What is the radius of convergence?

b) Determine (on the basis of the found generating function) an explicit formula for $p_n$.

Solution: Together with the initial conditions we have \begin{align*} P(x) &= 0 + x + \sum_{n=2}^{\infty} p_n x_n \\ &= x + \sum_{n=1}^{\infty} p_{n+1} x^{n+1} \\ &= x + \sum_{n=1}^{\infty} (2p_n + p_{n-1}) x^{n+1} \\ &= x + \sum_{n=1}^{\infty} 2p_n x^{n+1} + \sum_{n=1}^{\infty} p_{n-1} x^{n+1} \\ &= x + 2x \sum_{n=1}^{\infty} p_n x^n + x \sum_{n=1}^{\infty} p_{n-1} x^n. \end{align*} Now we look at each series separately to see what we've got. The first series on the left expands as $(x + p_2 x^2 + p_3 x^3 + ...)$. This is nothing but the original $P(x)$ (because we can ignore the constant term $0$ right?). So for the first series we've got $2x P(x)$.

The second series on the right expands as $(0 + x^2 + p_2 x^3 + ...)$. We can factorize $x$ out such that we get $P(x)$ again. So everything together we have: \begin{align*} P(x) = x + 2xP(x) + x^2 P(x), \end{align*} which gives us \begin{align*} P(x) (1-2x-x^2) = x, \end{align*} or \begin{align*} P(x) = \frac{x}{(1-2x-x^2)}. \end{align*}

But then I don't know how to determine the radius of convergence, and how to do b). Any help would be appreciated.

• Bell numbers are something completely different. – Lucian Jan 28 '15 at 15:57
• I know, I had written 'Pell' numbers first but someone edited it for me... – Kamil Jan 28 '15 at 16:02
• @Lucian: It is my mistake! Thanks for correcting that. – Mhenni Benghorbal Jan 28 '15 at 16:02
• @Kamil $(1-2x-x^2) \neq -(1+x)^2$ – rlartiga Jan 28 '15 at 16:12
• @rlartiga. Thanks, typed in the wrong expression in Maple. – Kamil Jan 28 '15 at 16:20

The radius of convergence is the distance to the nearest singularity

For $(b)$ you can advance as (based on your calculations) using partial fraction

$$P(x)= \frac{x}{(1-2x-x^2)}= \frac{A}{x-a} + \frac{B}{x-b}$$

where $a,b$ are the roots of $1-2x-x^2$ and $A$ and $B$ need to be determined. The calculations gives:

$$\frac{-1-\sqrt{2}}{2 \sqrt{2} (x+\sqrt{2}+1)}+\frac{1-\sqrt{2}}{2 \sqrt{2} (x-\sqrt{2}+1)}$$

Then use the geometric series expansion.

Note:

$$\frac{1}{a-t} = \frac{1}{a}\sum_{n=0}^{\infty} \frac{t^n}{a^n}$$

• $1-2x-x^2 \neq (1-x)^2$ – rlartiga Jan 28 '15 at 16:01
• @rlartiga: It is a typo! Thank you! – Mhenni Benghorbal Jan 28 '15 at 16:03
• What do you mean with singularity? – Kamil Jan 28 '15 at 16:21
• @Kamil: Where the function blows up? For instance what's the singularity of $\frac{1}{1-x}$? So you can see the radius of convergence? – Mhenni Benghorbal Jan 28 '15 at 16:22
• @MhenniBenghorbal I put the calculation of the partial decompostion. Feel free to change it. – rlartiga Jan 28 '15 at 16:24

The terms in your sum are $p_nx^n$. If you solve the recurrence relation, you can find that $p_n$ grows as $r^n$ for some $r$, the larger root of the characteristic equation. You need the terms to decease faster than $\frac 1n$, so need $|x| \lt \frac 1r$