1
$\begingroup$

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.

Please help me to solve it using less complex way

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ but in answer $p=q=n+1$ $\endgroup$ – jacky Feb 17 at 7:06
  • $\begingroup$ 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$. $\endgroup$ – Servaes Feb 17 at 11:01

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.