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.

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


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

| cite | improve this answer | |
  • 1
    $\begingroup$ $1-2x-x^2 \neq (1-x)^2$ $\endgroup$ – rlartiga Jan 28 '15 at 16:01
  • $\begingroup$ @rlartiga: It is a typo! Thank you! $\endgroup$ – Mhenni Benghorbal Jan 28 '15 at 16:03
  • $\begingroup$ What do you mean with singularity? $\endgroup$ – Kamil Jan 28 '15 at 16:21
  • $\begingroup$ @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? $\endgroup$ – Mhenni Benghorbal Jan 28 '15 at 16:22
  • 1
    $\begingroup$ @MhenniBenghorbal I put the calculation of the partial decompostion. Feel free to change it. $\endgroup$ – 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$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.