Finding the closed formula for $A_n + B_n$ for recursions $A_n$ and $B_n$

Question

Update: I made a mistake when posting this question - the recursive definition in $\text{(A)}$ was defined with

$\tag A A_{n+1} = (n-1)A_n + 2B_n \quad \quad \text{ERROR}$

and has now been corrected.

I checked and the recursion now agrees with the solution to the motivating problem linked to below.

The prior question was well founded and had two answers, with Calvin Lin solving it. Olivier Roche supplied hints using matrix methods.

I know I could have posted a new question, but figured this edit made the most sense.

---

Define $A_4 = 0$ and $B_4 = 2$.

For $n \ge 4$ define

$\tag A A_{n+1} = (n-1)A_n + 4B_n$

and

$\tag B B_{n+1} = (n-2) B_n$

Find an explicit formula in $n$ to represent the sum $A_n + B_n$ for $n \ge 5$.

My Work

I answered a combinatorial question on this site and wanted to use this method, but I'm not sure how to proceed. Using a combinatorial argument I verified the recursion holds, and want to apply the appropriate techniques to get the answer in a different way.

Answer 1

Write $X_n := \begin{pmatrix} A_n \\ B_n \end{pmatrix}$ and $M_n := \begin{pmatrix} (n-1) & \mathbf{4} \\ 0 & (n-2) \end{pmatrix}$, this allows you to sum up the recurrence relation as : $$\boxed{X_{n+1} = M_n X_n}$$

In other words, one has $X_n = (\prod_{k=4}^n M_k)X_4 $. Your goal is now to express $P_n :=(\prod_{k=4}^n M_k)$ with a closed formula.

conjecture1 (wrong) for $n\geqslant 5$, one has $$P_n = \begin{pmatrix} (n-1)! & n(n-1)-12\\ 0 & (n-2)! \end{pmatrix} $$

New try (one should be able to solve the problem without knowing $\star$) :

conjecture2 for $n\geqslant 4$, $P_n$ is of the form $$P_n = \begin{pmatrix} \frac{(n-1)!}{2} & \star\\ 0 & (n-2)! \end{pmatrix} $$

Answer 2

By looking at initial terms and using induction, we can conclude that $A_n + B_n = 2 \times (n-3) \times (n-3)!$, $A_n = 2(n-4)(n-3)!$, $B_n = 2(n-3)!$.

Here is a combinatorial approach, but it is very contrived.

For a permutation $ \rho \in S_{n-2}$, count the number of pairs $(a_i, a_{i+1})$ such that $\rho(a_i ) - \rho (a_{i+1} $ are consecutive integers.
There are $n-3$ pairs of consecutive integers, and they are consecutive in $2\times (n-3)!$ ways, which means that there are a total of $2\times (n-3) \times (n-3)!$ such pairs.

Alternatively, let $B_n$ be the number of ways that a permutation of $S_{n-2}$ has "1,2" consecutive. Given any way for $B_n$, there are $n-2$ places we can insert the value $n-1$ in the permutation to obtain a way for $B_{n+1}$.
This is clearly a bijection so $B_{n+1} = (n-2) B_n$.
We can verify that $B_4 = 2$.

Let $A_n$ be the number of ways that a permutation of $S_{n-2}$ has "2,3" or "3,4", or ..., or "$n-3, n-2$" consecutive, counted with duplicity.
We have $A_n = (n-4) B_n$ by counting the number of pairs.
Hence $A_{n+1} = (n-3) B_{n+1} = (n-3) (n-2) B_n = (n-1)(n-4)B_n + 2B_n = (n-1)A_{n} + 2B_n$.
We can verify that $A_4 = 0$.

Hence, $A_n+ B_n = 2 \times (n-3) \times (n-3)!$.

Answer 3

Using Olivier Roche matrix technique, we define for $n \ge 4$

$$P_n = \begin{pmatrix} \frac{(n-1)!}{2} & p_n\\ 0 & (n-2)! \end{pmatrix} $$

where $p_n$ is, to start with, unknown, but $p_4 = 4$.

Set

$$M_{n+1} = \begin{pmatrix} n & 4\\ 0 & n-1 \end{pmatrix} $$

Multiplying $M_{n+1} \circ P_n$ to get $P_{n+1}$ we conclude that

$\tag 1 p_{n+1} = n p_n + 4 \, (n-2)!$

Handing this off to wolframalpha, the recurrence equation solution is given by

$\quad p_n = \bigr ( (c_1 + 4) n - c_1 - 8 \bigr ) Γ(n - 1) \quad \text{ (where } c_1 \text{ is an arbitrary parameter)}$

We can solve for $c_1$ knowing that $p_4 = 4$ and find that $c_1 = -2$.

So for $n \ge 4$ we can write

$\tag 2 p_n = 2 (n-3) \, (n-2)!$

By applying the matrix $P_n$ to the vector

$$ \begin{bmatrix} 0 \\ 2 \end{bmatrix} $$

we conclude that, for $n \ge 4$,

$\quad A_{n+1} = 2 * p_n = 4 (n-3) \, (n-2)!$

and

$\quad B_{n+1} = 2 * (n-2)!$