¿Cómo resuelve esta recurrencia [matemática] T (n) = T \ left (\ left \ lfloor \ frac {n} {4} \ right \ rfloor \ right) + n [/ math] por método de sustitución?
[editar: dejé mi trabajo original al final de esta respuesta; ahora que he tenido un poco más de tiempo para procesar esto, aquí hay una prueba de inducción de la solución explícita dada (independientemente) por Bryan Wang y David Pement: con [matemáticas] T (0) = c [/ matemáticas], tenemos
[matemáticas] T (n) = c + n + \ lfloor n / 4 \ rfloor + \ lfloor n / 16 \ rfloor + \ lfloor n / 64 \ rfloor + \ dots = c + \ displaystyle \ sum_ {j = 0} ^ \ infty \ lfloor n / 4 ^ j \ rfloor \ tag {*} [/ math]
Aunque esto se escribe como una suma infinita, para cualquier opción de [matemática] n [/ matemática], los términos desaparecen cuando [matemática] 4 ^ j> n [/ matemática], por lo que para cualquier elección de [matemática] n [/ matemática], solo necesitamos agregar hasta [math] j = \ lfloor \ log_4 n \ rfloor [/ math] términos.
- Cómo multiplicar enteros de dos grupos permutablemente
- En términos simples, ¿por qué es difícil factorizar el producto de dos números primos grandes?
- Cómo resolver este problema de manera eficiente (sin adivinar y verificar)
- Cómo resolver 2 ^ (n-1) = (n ^ 4-6n ^ 3 + 23n ^ 2-18n + 24) / 24 analíticamente
- Cómo resolver este algoritmo (estrategia óptima)
Noté en mi trabajo anterior (abajo) que [matemáticas] T (4 ^ k) = c + \ frac {1} {3} (4 ^ {k + 1} -1) [/ matemáticas]. No es demasiado difícil confirmar que esto es consistente con [math] (*) [/ math], porque [math] \ sum_ {j = 0} ^ \ infty \ lfloor 4 ^ k / 4 ^ j \ rfloor = \ sum_ {j = 0} ^ k 4 ^ {kj} = 1 + 4 + 4 ^ 2 + \ cdots + 4 ^ k [/ math].
Deje que [math] S_k [/ math] sea la declaración “formula [math] (*) [/ math] tiene para [math] n \ le 4 ^ k [/ math]”. Es fácil confirmar [math] S_0 [/ matemática]: [matemática] T (0) = c [/ matemática] y [matemática] T (1) = c + 1 [/ matemática].
Ahora suponga que [math] S_k [/ math] se cumple para algunos [math] k \ ge 0 [/ math]. Queremos probar [matemáticas] S_ {k + 1} [/ matemáticas], es decir, que [matemáticas] (*) [/ matemáticas] también es válido para [matemáticas] 4 ^ k <n \ le 4 ^ {k + 1} [/ matemáticas]. Para tal valor de [matemática] n [/ matemática], [matemática] m = \ lfloor n / 4 \ rfloor [/ matemática] está entre [matemática] 4 ^ {k-1} [/ matemática] y [matemática] 4 ^ k [/ math] inclusive (entonces [math] S_k [/ math] aplica). Además, si [math] f = n \ mod 4 [/ math] y [math] j \ ge 0 [/ math], entonces
[matemáticas] \ left \ lfloor \ dfrac {n} {4 ^ {j + 1}} \ right \ rfloor = \ left \ lfloor \ dfrac {4m + f} {4 ^ {j + 1}} \ right \ rfloor = \ left \ lfloor \ dfrac {m} {4 ^ j} \ right \ rfloor [/ math]
Por lo tanto,
[matemáticas] \ begin {align} T (n) & = n + T (m) \\ & = \ lfloor n / 4 ^ 0 \ rfloor + c + \ sum_ {j \ ge 0} \ lfloor m / 4 ^ j \ rfloor \\ & = c + \ lfloor n / 4 ^ 0 \ rfloor + \ sum_ {j \ ge 1} \ lfloor n / 4 ^ j \ rfloor \\ & = c + \ sum_ {j \ ge 0} \ lfloor n / 4 ^ j \ rfloor \ end {align} [/ math]
[sigue la respuesta original]
Para encontrar una forma cerrada, elija [math] T (0) = c [/ math] como punto de partida, con [math] c [/ math] como entero. (La última suposición no es necesaria, pero simplifica un poco la discusión subsiguiente.) Luego tenemos inmediatamente (por ejemplo) [matemáticas] T (1) = c + 1 [/ matemáticas], [matemáticas] T (2 ) = c + 2 [/ matemática], [matemática] T (3) = c + 3 [/ matemática] y [matemática] T (4) = c + 5 [/ matemática].
La apariencia de la función de piso hace que el método de sustitución sea un poco complicado aquí. Se me ocurrieron algunas ideas investigando los primeros cientos de términos (usando una hoja de cálculo).
Comience considerando [math] n = 4 ^ k [/ math] para el entero [math] k \ ge0 [/ math]:
[matemáticas] T (4 ^ k) = T (4 ^ {k-1}) + 4 ^ k = T (4 ^ {k-2}) + 4 ^ {k-1} + 4 ^ k = \ cdots \\\ qquad = T (0) + 1 + 4 + 4 ^ 2 + \ cdots + 4 ^ {k-1} + 4 ^ k \\\ qquad = c + \ dfrac {4 ^ {k + 1} -1 } {4-1} [/ matemáticas]
Ahora, al examinar la secuencia, podemos ver que si [matemática] n = 4j [/ matemática] es un múltiplo de 4, entonces [matemática] T (n), T (n + 1), T (n + 2 ), T (n + 3) [/ math] son cuatro enteros consecutivos (si [math] c [/ math] es un entero). Por ejemplo, si [matemática] c = 10 [/ matemática], entonces [matemática] T (20), \ puntos, T (23) [/ matemática] son 36,37,38,39. Probar esto es bastante simple:
- [matemática] T (n) = T (j) + n [/ matemática], y para [matemática] i \ in \ {1,2,3 \} [/ matemática], [matemática] T (n + i) = T (4j + i) = T (j) + n + i = T (n) + i [/ matemáticas].
Tengo más que decir, pero (por el momento) no hay más tiempo para decirlo. Intentaré volver a esta respuesta más tarde, aunque para entonces alguien más podría haber publicado una respuesta más detallada.