Cada entero positivo [matemática] N [/ matemática] es trivialmente una suma de términos de la secuencia [matemática] \ {1,2,3, \ ldots \} [/ matemática], y hay varias formas de hacerlo, a menos que [matemáticas] N = 1 [/ matemáticas]. Lo mismo ocurre con la representación de [math] N [/ math] por la secuencia [math] \ {1,2,2 ^ 2,2 ^ 3, \ ldots \} [/ math]. En este caso, sin embargo, la representación es única . Esta es la base para poder escribir [matemáticas] N [/ matemáticas] en la base dos. La existencia de tal representación garantiza una representación de base dos (esto es solo una nueva redacción), la unicidad hace que esta representación sea una función.
La conocida secuencia de Fibonacci [matemática] \ {F_n \} _ {n \ ge 1} [/ matemática], dada por
[matemática] F_n = F_ {n-1} + F_ {n-2} [/ matemática] para [matemática] n \ ge 3, F_1 = 1, F_2 = 1 \ ldots (1) [/ matemática]
comparte la propiedad de representar cada [matemática] N [/ matemática] como una suma de términos de la secuencia. Si eliminamos el primer término [matemática] F_1 = 1 [/ matemática] de la secuencia, [matemática] N [/ matemática] aún puede expresarse como una suma de términos distintos de la secuencia de Fibonacci. Visto así, la secuencia [math] \ {F_n \} _ {n \ ge 2} [/ math] se comporta como la secuencia [math] \ {2 ^ n \} _ {n \ ge 0} [/ math].
- ¿Es X un número entero?
- Cómo encontrar el resto de 2 ^ 55 dividido por 33
- ¿Cuál es el resto de 88 ^ 77/77?
- ¿Puedes probar 2 = 1?
- Sea f (n) yg (n) igual al número de números primos menores que n = 3mod4 y = 1mod4 respectivamente. ¿Qué es [math] lim_ {n \ to \ infty} \ frac {f (n)} {g (n)} [/ math]?
Para ver esto, simplemente podemos usar el algoritmo [math] “[/ math] greedy [math]” [/ math] – dado [math] N \ in \ mathbb N [/ math], elija el término más grande en la secuencia que no exceda [matemática] N [/ matemática], es decir, elija [matemática] n [/ matemática] tal que [matemática] F_n \ le N <F_ {n + 1} [/ matemática]. Si [math] N-F_n = 0 [/ math], hemos terminado con la representación. De lo contrario [matemática] 0 <N-F_n <F_ {n + 1} -F_n = F_ {n-1} [/ matemática], y así tenemos
[matemática] N = F_ {n_1} + F_ {n_2} + F_ {n_3} + \ cdots + F_ {n_r} [/ matemática], con cada [matemática] n_k – n_ {k + 1}> 1 \ ldots ( 2) [/ matemáticas]
por inducción matemática . Por cierto, el mismo argumento (uso del algoritmo codicioso junto con la inducción matemática) también muestra que cada [matemática] N [/ matemática] puede escribirse como una suma de términos distintos de la secuencia [matemática] \ {1,2,2 ^ 2,2 ^ 3, \ ldots \} [/ math]. Sin embargo, en este caso en la representación
[matemáticas] N = 2 ^ {n_1} + 2 ^ {n_2} + 2 ^ {n_3} + \ cdots + 2 ^ {n_r} \ ldots (3) [/ matemáticas]
a veces ocurre que una o más de las diferencias [matemáticas] n_k-n_ {k + 1} = 1 [/ matemáticas].
La singularidad en la ecuación. [matemáticas] (2) [/ matemáticas] es una consecuencia del hecho de que
[matemática] \ displaystyle \ sum_ {k = 2} ^ n F_k = F_ {n + 2} -2 [/ matemática] para cada [matemática] n \ ge 2 [/ matemática],
y la unicidad en eqn. [matemáticas] (3) [/ matemáticas] es una consecuencia del hecho de que
[matemática] \ displaystyle \ sum_ {k = 0} ^ n 2 ^ k = 2 ^ {n + 1} -1 [/ matemática] para cada [matemática] n \ ge 0 [/ matemática].
(Dejo la prueba de la parte de singularidad al lector interesado).
Una secuencia completa es una secuencia [matemática] \ {s_n \} _ {n \ ge 1} [/ matemática] de enteros positivos de modo que cada [matemática] \ N \ en \ matemática N [/ matemática] puede expresarse como una suma de términos de la secuencia. Así
[matemáticas] N = \ displaystyle \ sum_ {n = 1} ^ {\ infty} {\ epsilon} _n \, s_n \ ldots (\ star) [/ math]
con cada [matemática] {\ epsilon} _n \ in \ {0,1 \} [/ math].
Si reorganizamos los términos de la secuencia para que no disminuya , es decir, [math] s_n \ le s_ {n + 1} [/ math] para cada [math] n [/ math], entonces está claro que es necesario condición para la representación en eqn. [math] (\ star) [/ math] para cada [math] N \ in \ mathbb N [/ math] es
- [matemáticas] s_1 = 1 [/ matemáticas], y
- [math] s_1 + s_2 + s_3 + \ cdots + s_n \ ge s_ {n + 1} -1 [/ math] para cada [math] n \ ge 1 [/ math].
El Criterio de Brown (1961) dice que esta condición obvia necesaria también es suficiente para que se complete la secuencia [math] \ {s_n \} [/ math].
Por lo tanto, tenemos una caracterización simple de todas las secuencias de enteros positivos para los cuales cada entero positivo es una suma de subsecuencia.
Observación. Esta es mi [matemáticas] 1000 \ text {th} [/ matemáticas] en aproximadamente [matemáticas] 9 [/ matemáticas] meses de escritura en Quora.