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

combinatoricsrecurrence-relations

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.

Best Answer

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} $$

Related Question