Encontrar la fórmula cerrada para An+BnAn+BnA_n + B_n para las recursiones AnAnA_n y BnBnB_n

Escribir$X_n := \begin{pmatrix} A_n \\ B_n \end{pmatrix}$y$M_n := \begin{pmatrix} (n-1) & \mathbf{4} \\ 0 & (n-2) \end{pmatrix}$, esto le permite resumir la relación de recurrencia como:

$$\boxed{X_{n+1} = M_n X_n}$$

En otras palabras, uno tiene$X_n = (\prod_{k=4}^n M_k)X_4$. Su objetivo ahora es expresar$P_n :=(\prod_{k=4}^n M_k)$con una fórmula cerrada.

conjetura1 (incorrecta) para$n\geqslant 5$, uno tiene

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

Nuevo intento (uno debería ser capaz de resolver el problema sin saber$\star$) :

conjetura2 para$n\geqslant 4$,$P_n$es de la forma

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

Al observar los términos iniciales y usar la inducción, podemos concluir que$A_n + B_n = 2 \times (n-3) \times (n-3)!$,$A_n = 2(n-4)(n-3)!$,$B_n = 2(n-3)!$.

Aquí hay un enfoque combinatorio, pero es muy artificial.

Para una permutación$\rho \in S_{n-2}$, cuenta el número de pares$(a_i, a_{i+1})$tal que$\rho(a_i ) - \rho (a_{i+1}$son enteros consecutivos.
Hay$n-3$pares de enteros consecutivos, y son consecutivos en$2\times (n-3)!$maneras, lo que significa que hay un total de$2\times (n-3) \times (n-3)!$tales pares.

Alternativamente, deje$B_n$Sea el número de formas en que una permutación de$S_{n-2}$tiene "1,2" consecutivos. Dada cualquier forma de$B_n$, hay$n-2$lugares donde podemos insertar el valor$n-1$en la permutación para obtener una forma de$B_{n+1}$.
Esto es claramente una biyección por lo que$B_{n+1} = (n-2) B_n$.
Podemos verificar que$B_4 = 2$.

Dejar$A_n$Sea el número de formas en que una permutación de$S_{n-2}$tiene "2,3" o "3,4", o..., o "$n-3, n-2$consecutivos, contados con duplicidad.
Tenemos$A_n = (n-4) B_n$contando el número de pares.
Por eso$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$.
Podemos verificar que$A_4 = 0$.

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

Utilizando la técnica matricial de Olivier Roche, definimos para$n \ge 4$

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

dónde$p_n$es, para empezar, desconocido, pero$p_4 = 4$.

Colocar

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

multiplicando$M_{n+1} \circ P_n$Llegar$P_{n+1}$concluimos que

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

Entregando esto a wolframalpha , la solución de la ecuación de recurrencia está dada por

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

podemos resolver para$c_1$sabiendo que$p_4 = 4$y encontrar que$c_1 = -2$.

Entonces para$n \ge 4$podemos escribir

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

Aplicando la matriz$P_n$al vector

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

concluimos que, para$n \ge 4$,

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

y

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