¿Por qué se puede reescribir así esta relación de recurrencia?

Question

Tengo la relación de recurrencia: $a(n)= a(\lfloor n/2 \rfloor)+a(\lceil n/2 \rceil)+3n+1$ con $a_1 =3$ . Esto se puede resolver para tener la fórmula explícita: $\frac{3\cdot log_2(n)\cdot n+4\cdot log_2(2)\cdot n - log_2(2)}{log_2(2)}$ . Simplemente estaba "jugando" con esta relación de recurrencia en el arce y descubrí que esta es su fórmula explícita. Luego me pregunté durante bastante tiempo acerca de cómo o por qué esta era su fórmula explícita. Entonces, ¿alguien puede mostrarme los pasos para llegar a ese resultado?

Answer 1

Deje $n=2^m$, a continuación, $a(2^m)= a(2^{m-1})+a(2^{m-1})+3·2^m+1$

Definir $b(m)=a(2^m)$, por lo que tenemos $b(m)=2b(m-1)+3·2^m+1$

Este es un homogénea lineal de la recurrencia de la ley. Este tipo de secuencias que tienen como explícito fórmula de la suma de la solución general de la homogénea de la ley y una solución particular de la no homogénea.

Vamos a tratar de $b(m)=Ar^m$, para algunas de las $A$ e $r$, para la homogénea:

$Ar^m=2Ar^{m-1}$ sólo es posible si $r=2$

Para la no homogénea, vamos a tratar de $b(m)=Dm2^m+E$. Sustituyendo en la recurrencia de la relación obtenemos $D=3$ e $E=-1$. Así,

$b(m)=A2^m+3m2^m-1$

Ahora, con la condición de $b(0)=3$ (debido a $a(2^0)=3$), podemos encontrar $A$: $3=A-1$ o $A=4$

$b(m)=4·2^m+3m2^m-1$

$a(n)=b(\log_2n)=4n+3n\log_2n-1$

como era de esperar.