# 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,$

which establishes (1).$ The Perrin sequence$\{P_n\}$is known to be prime-divisible which means that for any prime index$p,p|P_p.$I'll give two proofs of the fact. ### Proof 1 So let$p$be a prime integer. By the Multinomial theorem (a generalization of the Binomial Theorem),$\displaystyle (r_{1}+r_{2}+r_{3})^{p}=\sum_{a+b+c=p}\frac{p!}{a!b!c!}r_{1}^{a}r_{2}^{b}r_{3}^{c},$where$a,b,c\ge 0.$The multinomial coefficient$C(a,b,c)=\displaystyle\frac{p!}{a!b!c!}$is always an integer and is divisible by$p,$except when to of$a,b,c$are zero. It follows that$\begin{align}\displaystyle (r_{1}+r_{2}+r_{3})^{p} &= \sum_{a+b+c=p-1}\frac{p!}{a!b!c!}r_{1}^{a}r_{2}^{b}r_{3}^{c}+(r^{p}_{1}+r^{p}_{2}+r^{p}_{3})\\ &= pz+(r^{p}_{1}+r^{p}_{2}+r^{p}_{3}), \end{align}$for an integer$z.$But$r_{1}+r_{2}+r_{3}=0$and$r^{p}_{1}+r^{p}_{2}+r^{p}_{3}=P_{p}$so that that can be rewritten as$P_{p}=-pz,$implying$p|P_{p}.$### Proof 2 Define a transformation$\tau$on$S_{n}$by shifting any integer$s\in\mathbb{N}_{n}$by 1:$\begin{cases} \tau (s)=s+1, & s\lt n,\\ \tau(n)=1. \end{cases}\tau(S)=\{\tau(s):\,s\in S\}.$It is obvious that$\tau(S)=S$is impossible for$S\in S_{n}$because, for$s\in S$that would imply$s+1\in S.$For$n=p, $a prime, we may claim more: For$S\in S_{p},\tau^{k}(S)=S,1\le k\le p,$only when$k=p.$That is, shifting$S$repeatedly returns to$S$only after$p$shifts. Indeed, let$1\le k\lt p$and$\tau^{k}(S)=S.p$being a prime,$k$and$p$are mutually prime such that there are integer$x$and$y,$with$xk+yp=1.$Now,$k$shifts, and, therefore,$xk$shifts, leave$S$invariant, as any multiple of$p$shifts, so that$\tau(S)=\tau^{xk+yp}(S)=S,$which is a contradiction. This actually implies that for any$S\in S_{p},$the sets$S,\tau (S),\tau^{2}(S),\ldots,\tau^{p-1}(S),$are not only distinct but also pairwise disjoint:$\tau^{k}(S)\cap\tau^{m}(S)=\emptyset,$for$1\le k,m\lt p,\,k\ne m.$In other words, the orbit under$\tau$of any$S\in S_p,$consists of$p$sets so that the whole of$S_p$splits into subsets of cardinality$p$each. This implies$p$divides$|S_{n}|.\$ ### 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 ### Combinatorial Proofs 