# Perrin Sequence

The main purpose of this page is to describe what's known as the Perrin sequence of integers $\{P_n\}$ which is defined recursively as follows:

(*)

$P_n= \begin{cases} 3 & \mbox{if } n = 0; \\ 0 & \mbox{if } n = 1; \\ 2 & \mbox{if } n = 2; \\ P_{n-2}+P_{n-3} & \mbox{if } n > 2. \\ \end{cases}$

Each member of the sequence is said to be a Perrin number. Here are the first few (this is the sequence A001608 in the Online Encyclopedia of Integer Sequences):

$3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39\ldots$

The Perrin sequence appears in several circumstances; I shall introduce one of these - a counting argument - that leads to the recurrence $P_n=P_{n-2}+P_{n-3}$.

Consider subsets of $\mathbb{N}_{n}=\{1,2,\ldots,n\},$ not all of them, though, but only those that do not contain even one pair of successive numbers, and among these only the maximal ones with that property, i.e., those to which adding an element would necessarily introduce a successive pair. The final stipulation is that the element $n$ is considered immediately following $1.$ Just for the convenience's sake, let's call such subsets "suitable." Let $S_n$ denote the set of all suitable subsets of $\mathbb{N}_{n}.$ E.g., $\{1,4,6\}\in S_{7},$ $\{2,4,6\}\in S_{7},$ $\{2,4,7\}\in S_{7}$ and also $\{2,4,7\}\in S_{8}$ but $\{1,4,7\}\notin S_{7};$ $\{1,4,7\}\in S_{8},$ and $\{1,4,7\}\in S_{9}.$ Note that a typical suitable sequence belongs to two successive sets $S_n.$ Let $C(n)=|S_{n}|,$ the number of elements in $S_{n}.$ We claim that

$C(n)=C(n-2)+C(n-3)$.

Let $S\in S_n.$ Assume the elements of $S$ are $\ldots\lt\ j\lt k,$ meaning that $k$ is the largest element of $S$ and that $j$ comes before $k$ in $S.$ It is then true that either $k=j+2$ or $k=j+3,$ because, by definition, we can't have $k=j+1,$ and $k=j+4$ would allow putting in an extra integer between $j$ and $k.$ Removing $k$ from $S$ leaves set $T$ say, with the largest element $j$ such that $T\in S_{n-2},$ if $k=j+2,$ or $T\in S_{n-3},$ if $k=j+3.$ Thus we uniquely associate elements of $S_n$ with elements from either $S_{n-2}$ or $S_{n-3}.$ The uniqueness of that association may be unusual in that two different sequences may be associated with the same one, albeit in different sets $S_{k},$ which is important. For example, $\{2,4,7,9\}$ and $\{2,4,7,10\}$ both belong to $S_{10}.$ However, $\{2,4,7,9\}\mapsto\{2,4,7\}\in S_{8}$ whereas $\{2,4,7,10\}\mapsto\{2,4,7\}\in S_{7}.$ However, to repeat, no two distinct elements in the same $S_n$ map on the same element in the same $S_k$ which assures us that it is possible to define the inverse association and thus prove the recursion.

Finally, it is obvious that $C(2)=2,$ $C(3)=3,$ $C(4)=2$ which makes $C(n)=P_{n},$ for $n\ge 2.$

The characteristic equation of the Perrin sequence

$x^{3}-x-1=0$

has three roots, say, $r_1,$ $r_2,$ and $r_3,$ implying that $P_{n}=Ar_{1}^{n}+Br_{2}^{n}+Cr_{3}^{n},$ where $A,B,C$ are real coefficients (although two of the roots are complex). We'll prove that in fact

(1)

$P_{n}=r_{1}^{n}+r_{2}^{n}+r_{3}^{n}.$

Suffice it to verify (1) for the first three terms of the sequence. For $n=0$ this is immediate:

$r_{1}^{0}+r_{2}^{0}+r_{3}^{0} = 3 = P_{0}.$

From Viète's formulas,

$r_{1}+r_{2}+r_{3}=0\\ r_{1}r_{2}+r_{2}r_{3}+r_{3}r_{1}=-1\\ r_{1}r_{2}r_{3}=1.$

Thus, for $n=1,$ $r_{1}+r_{2}+r_{3}=0=P_{1}.$ For $n=2,$ we have

$r_{1}^{2}+r_{2}^{0}+r_{2}^{0} = (r_{1}+r_{2}+r_{3})^{2}-2(r_{1}r_{2}+r_{2}r_{3}+r_{3}r_{1})=2,$

### References

1. M. Erickson, Beautiful Mathematics, MAA, 2011, p 99
2. G. Minton, Three Approaches to a Sequence Problem, Mathematics Magazine, VOL. 84, NO. 1, February 2011, 33-37