Given the permutation recurrence relation find $a_n$

Question

In bell ringing, successive permutations of n bells are played one after the other. Following one permutation π, the next permutation must be obtained from π by moving the position of each bell by at most one place. For example, for n = 4, the permutation 1234 could be followed by any one of 2134,2143,1324, 1243. Show that if a_n denotes the number of permutations which could follow 12...n, then a_n = a_n-1 + a_n-2 + 1. Hence find a_n.

-Have absolutely no idea how to approach this problem, any help is appreciated.

Answer 1

Suppose that $n\ge 3$. There are $a_{n-1}$ permutations that can follow $12\ldots n$ that end in $n$. Alternatively, we can take any legitimate permutation of $12\ldots(n-2)$ and follow it with $n(n-1)$; that’s another $a_{n-2}$ permutations. Can you find the one remaining permutation that can follow $12\ldots n$? HINT: It ends in $n(n-1)$.

Once you’ve established the recurrence with suitable initial conditions, you’re supposed to solve it. If you’ve studied generating functions, you can use that approach to solve it mechanically. If not, I suggest that you write out the first nine terms or so and try to find a simple relationship between them and a known sequence. I’ve added a further hint in the spoiler-protected block below.

Add $1$ to each and see if you recognize the resulting numbers.

Answer 2

Let us make the problem more general considering the recurrence $$a_n=\alpha a_{n-1}+\beta a_{n-2}+k$$ in which $k$ is a known constant.

Define $a_n=b_n+c$ and replace. So, the relation becomes $$b_n+c=\alpha (b_{n-1}+c)+\beta (b_{n-2}+c)+k=\alpha b_{n-1}+\beta b_{n-2}+(\alpha +\beta) c+k$$ So, setting $$c=(\alpha +\beta) c+k$$ that is to say $$c=\frac k {1-\alpha -\beta}$$ reduces the recurrence equation to $$b_n=\alpha b_{n-1}+\beta b_{n-2}$$ which is simple.

In your case, $\alpha=1$, $\beta =1$, $k=1$ then $c=-1$.

I am sure that you can take from here.