Fibonacci y lanzar monedas

Question

Consideremos el siguiente esquema a partir de una secuencia $\sigma_0 = \langle 1,1,\dots,1\rangle$ de longitud $k$ seguidas sucesivamente por secuencias $\sigma_i$ de la misma longitud pero desplazado uno a la derecha, donde la primera entrada $\sigma_{i0}$ es igual a la suma de todos los valores anteriores, y $\sigma_{ij} = \sigma_{i0}$ .

Para $k = 5$ uno tiene:

 1  1  1  1  1                        
    1  1  1  1  1                     
       2  2  2  2  2                  
          4  4  4  4   4             
             8  8  8   8   8          
               15 15  15  15  15      
                  29  29  29  29  29  
                      56  56  56  56  56
                         108 108 108 108 108
                             208 208 208 208 208

Calculando la suma para cada columna se obtiene, por ejemplo, para $k = 5$ :

 1  2  4  8 16 30 58 112 216 416 802 1546 2980 5744 ...

Resulta que para $k = 3$ y $k = 4$ estas secuencias, a saber

1 2 4 6 10 16 26 42 68 110 178 288 466 754 1220 1974 ...

et

1 2 4 8 14 26 48 88 162 298 548 1008 1854 3410 6272 ...

parecen ser el número de maneras de lanzar una moneda $n$ veces y no conseguir una racha de $k$ (véase A128588 y A135491 ).

Conjetura : Esto es válido en general, es decir, para cualquier $k$ .

Mi pregunta es doble:

1. ¿Cómo demostrar esta conjetura?

2. ¿Qué tienen que ver los esquemas anteriores con lanzar una moneda al aire y contar carreras?

Adivina : Cuando intentas calcular el número de formas de lanzar una moneda $n$ veces y no conseguir una racha de $k$ se te pueden ocurrir esos planes. ¿Pero cómo?

---

Obsérvese que la secuencia para $k=3$ ( A128588 ) resulta ser el doble de los números de Fibonacci.

Los esquemas surgieron cuando intenté imitar la propagación epidémica en un modelo discreto tipo SIR (véase aquí ).

Answer 1

Aquí tienes otra forma de construir tu secuencia. Deje que $a^k$ sea la secuencia definida por $$a^k_n=a^k_{n-1}+a^k_{n-2}+\cdots+a^k_{n-k+1}$$ para $n\geq k$ et $$a^k_n=2^n$$ para $$0\leq n < k$$

Esencialmente se trata de una generalización de la sucesión de fibonacci en la que los términos iniciales son potencias de $2$ y los términos sucesivos son la suma de los anteriores $k-1$ entradas.

¿Qué tiene que ver esto con las monedas y las carreras? Veamos primero el caso $k=2$ . $$a^2:1,2,2,2,...,2$$ Para crear una secuencia de $n$ lanzamientos de moneda sin una racha de $2$ primero debe crear una secuencia de $n-1$ lanzamientos de moneda sin una racha de $2$ y, a continuación, se le obliga a elegir cara o cruz en función de la última entrada en este $n-1$ secuencia.

Qué ocurre en el caso $k=3$ ? $$a^3:1,2,4,6,10,16,...$$ Para contar el número de formas de crear una secuencia de $n$ lanzamientos de moneda sin una racha de $3$ puede dividirlo en dos preguntas más sencillas: 1) ¿Cuántos $n$ secuencias sin $3$ -tienen una cola de $1$ -¿correr? Y 2) ¿Cuántos $n$ secuencias sin $3$ -tienen una cola de $2$ -¿Corre? Las respuestas respectivas son 1) el número de formas en que puede crear $n-1$ secuencias sin $3$ -y 2) el número de formas de crear $n-2$ secuencias sin $3$ -corre.

En el caso general, para contar el número de $n$ secuencias sin $k$ -dividir la pregunta en una serie de preguntas más pequeñas: ¿Cuántos $n$ secuencias sin $k$ -ejecutar tienen un $1$ -¿Correr al final? Y así sucesivamente hasta preguntar cuántos $n$ secuencias sin $k$ -runs han $k-1$ ¿corre al final? Así que contando el número de $n$ secuencias sin $k$ - sólo equivale a sumar las anteriores $k-1$ condiciones.

Si algo de lo que he escrito es confuso, hágamelo saber e intentaré explicarme mejor.