Actualización: cometí un error al publicar esta pregunta: la definición recursiva en se definió con
y ahora ha sido corregido.
Verifiqué y la recursividad ahora está de acuerdo con la solución al problema motivador vinculado a continuación.
La pregunta anterior estaba bien fundada y tenía dos respuestas, resolviéndola Calvin Lin. Olivier Roche proporcionó sugerencias utilizando métodos matriciales.
Sé que podría haber publicado una nueva pregunta, pero pensé que esta edición tenía más sentido.
Definir y .
Para definir
y
Encuentre una fórmula explícita en para representar la suma para .
Mi trabajo
Respondí una pregunta combinatoria en este sitio y quería usar este método, pero no estoy seguro de cómo proceder . Usando un argumento combinatorio, verifiqué que la recursividad se mantiene y quiero aplicar las técnicas apropiadas para obtener la respuesta de una manera diferente.
Escribir y , esto le permite resumir la relación de recurrencia como:
En otras palabras, uno tiene . Su objetivo ahora es expresar con una fórmula cerrada.
conjetura1 (incorrecta) para , uno tiene
Nuevo intento (uno debería ser capaz de resolver el problema sin saber ) :
conjetura2 para , es de la forma
Al observar los términos iniciales y usar la inducción, podemos concluir que , , .
Aquí hay un enfoque combinatorio, pero es muy artificial.
Para una permutación
, cuenta el número de pares
tal que
son enteros consecutivos.
Hay
pares de enteros consecutivos, y son consecutivos en
maneras, lo que significa que hay un total de
tales pares.
Alternativamente, deje
Sea el número de formas en que una permutación de
tiene "1,2" consecutivos. Dada cualquier forma de
, hay
lugares donde podemos insertar el valor
en la permutación para obtener una forma de
.
Esto es claramente una biyección por lo que
.
Podemos verificar que
.
Dejar
Sea el número de formas en que una permutación de
tiene "2,3" o "3,4", o..., o "
consecutivos, contados con duplicidad.
Tenemos
contando el número de pares.
Por eso
.
Podemos verificar que
.
Por eso, .
Utilizando la técnica matricial de Olivier Roche, definimos para
dónde es, para empezar, desconocido, pero .
Colocar
multiplicando Llegar concluimos que
Entregando esto a wolframalpha , la solución de la ecuación de recurrencia está dada por
podemos resolver para sabiendo que y encontrar que .
Entonces para podemos escribir
Aplicando la matriz al vector
concluimos que, para ,
y
Azlif
copiarpegar
calvin lin
copiarpegar