# recursive relation on derangement of objects

Let $$a_{n}$$ represent the number of derangements of $$n$$ objects . If $$a_{n+2}=p a_{n+1}+q a_{n}\;\forall n\in\mathbb{N}$$ then what is $$\displaystyle \frac{q}{p}$$?

What I have tried:

I have used $$a_{n}=n!\bigg[1-\frac{1}{1!}+\frac{1}{2!}+\cdots +(-1)^n\frac{1}{n!}\bigg],$$ $$a_{n+1}=n!\bigg[1-\frac{1}{1!}+\frac{1}{2!}+\cdots +(-1)^{n+1}\frac{1}{(n+1)!}\bigg],$$ $$a_{n+2}=n!\bigg[1-\frac{1}{1!}+\frac{1}{2!}+\cdots +(-1)^{n+2}\frac{1}{(n+2)!}\bigg],$$

and comparing coefficients but it is very lengthy.

The question implicitly seems to assume that there exist $$p$$ and $$q$$ that satisfy this relation for all $$n$$. Then in particular they must satisfy it for $$n=1$$ and $$n=2$$. This gives you two linear equations in $$p$$ and $$q$$ that are easily solved: For $$n=1$$ and $$n=2$$ you get $$2=1\cdot p+0\cdot q\qquad\text{ and }\qquad 9=2p+q,$$ so $$p=2$$ and $$q=5$$. However, plugging in $$n=3$$ shows that $$44\neq 2\cdot9+5\cdot2,$$ so the premise of the question is false.
If $$p$$ and $$q$$ are allowed to depend on $$n$$, the question remains ill-posed; for $$n=2$$ the relation $$9=2p+q,$$ holds for $$(p,q)\in\{(0,9),(1,7),(2,5),(3,3),(4,1)\}$$ each yielding different values for $$\frac{p}{q}$$.
The solution that whomever gave you the question may have had in mind is the following: As $$a_{n}=n!\left(1-\frac{1}{1!}+\frac{1}{2!}+\cdots +(-1)^n\frac{1}{n!}\right)=n!\sum_{k=0}^n\frac{(-1)^k}{k!},$$ for all $$n\in\Bbb{N}$$, it follows that $$\begin{eqnarray*} a_{n+1} &=&(n+1)!\left(1-\frac{1}{1!}+\frac{1}{2!}+\cdots +(-1)^n\frac{1}{(n+1)!}\right) &=&(n+1)!\sum_{k=0}^{n+1}\frac{(-1)^k}{k!},\\ &=&(n+1)\cdot n!\left(1-\frac{1}{1!}+\frac{1}{2!}+\cdots +(-1)^n\frac{1}{(n+1)!}\right) &=&(n+1)\cdot n!\sum_{k=0}^{n+1}\frac{(-1)^k}{k!}\\ &=&(n+1)\cdot\left(a_n+n!\frac{(-1)^{n+1}}{(n+1)!}\right) =(n+1)a_n+(-1)^{n+1}. \end{eqnarray*}$$ We can use this identity twice to express $$a_{n+2}$$ in terms of $$a_n$$ and $$a_{n+1}$$ as follows $$\begin{eqnarray*} a_{n+2} &=&(n+2)a_{n+1}+(-1)^{n+2}\\ &=&(n+1)a_{n+1}+(-1)^{n+2}+a_{n+1}\\ &=&(n+1)a_{n+1}-(-1)^{n+1}+(n+1)a_n+(-1)^{n+1}\\ &=&(n+1)(a_{n+1}+a_n), \end{eqnarray*}$$ so in deed $$p=q=n+1$$ is a valid solution, though just one of many.
• but in answer $p=q=n+1$ – jacky Feb 17 at 7:06
• Sure, that's also an option. The point is that there are many options; in fact for any choice of $p$ you can take $$q:=\frac{a_{n+2}-pa_{n+1}}{a_n},$$ and the relation will hold. Even if you require $p$ and $q$ to be integers, the example I gave for $n=2$ shows that there are many options for $p$ and $q$. – Servaes Feb 17 at 11:01