Búsqueda de $\Theta$ de Recurrencia $ T(n) = 2T(\frac{n}{3})+2T(\frac{2n}{3})+n$ o encontrar la Forma Cerrada para $2^{p+1}+2=3^p$

Question

El objetivo es conseguir una exacta asintótica para $T(n).$ traté de dos enfoques, pero ambos fallaron:

1). La recursividad árbol. Vemos que $$\sum_{i = 0}^{\log_{3}(n)}n2^i=\Theta(n^{1+\log_3(2)})<<T(n) << \sum_{i = 0}^{\log_{3/2}(n)} n2^i = \Theta(n^{1+\log_{3/2}(2)})$$ but cannot, as I can see, get $\Theta(T(n))$ exactamente.

2). Akra-Bazzi Teorema. Podemos llegar a través de sencillos de cálculo que $T(n) = \Theta(n^p)$ donde $2+2^{p+1} = 3^p$. Tan lejos como puedo ver esta ecuación no da la forma cerrada para $p\,$ (Pero da una aproximación numérica consistente con 1, por lo que es bueno).

El objetivo es conseguir una forma cerrada mejor que $2^{p+1}+2 = 3^p.$ creo tal forma cerrada no existe, por razones asociadas con la espera de la dificultad del problema, y que puede ser encontrado a través de una alternativa de derivación, transformaciones o algún otro truco.

Resumen: Doble objetivo de la pregunta, la respuesta, la resolución será aceptada:

(1). Puede que este problema sea resuelto sin el uso de la Akra-Bazzi Teorema?

(2). Encontrar una mejor forma cerrada para $p$.

Esencialmente, tengo un presentimiento de que la obtención de (1) conduce a (2).

Cualquier ayuda es muy apreciada.

Este es el problema 2(m) de Jeffrey Erickson notas.

Answer 1

El objetivo es conseguir una forma cerrada mejor que $\,2+2^{p+1}=3^p\,$ es imposible, porque la $\,T(n)=An^p-n\,$ es la solución (y el Akra-Bazzi Teorema es no necesario para conseguir este).

E. g. la recursividad de los números de Fibonacci es un buen ejemplo de cómo obtener tales fórmulas. El enlace de arriba (Jeffrey Erickson notas) es demasiado bueno para entender cómo resolver este tipo de recursiones.

Para un cerrado formulario para $\,p\,$ definir una función $\,f(x):=\sqrt[x]{4\cosh x}\,$ $\,x>0\,$ $\,f^{-1}(x)\,$ es la función inversa de modo que se obtiene: $$p=\frac{2}{\ln 2}f^{-1}(\sqrt[\ln2]{4.5})$$

---

Hicimos $\,$me dio un buen consejo para añadir una prueba para el (descendente) de la monotonía de la $\,f(x)\,$ .

Es suficiente para la prueba esta de $\,\ln f(x)\,$ porque de $\displaystyle \frac{d}{dx}f(x)=f(x)\frac{d}{dx}\ln f(x)\,$$\,f(x)>0\,$ .

Tenemos a la prueba de $\,\displaystyle\frac{d}{dx}\ln f(x)<0\,$ todos los $\,x>0\,$ .

$\displaystyle\frac{d}{dx}\ln f(x)=-\frac{\ln (4\cosh x)}{x^2}+\frac{\tanh x}{x}<0\enspace$ es cierto porque de

$x\tanh x<x<\ln(2 e^x)<\ln(4\cosh x)\enspace$ o en los detalles

$e^x-e^{-x}<e^x+e^{-x}\,$ , $\enspace x<x+\ln 2\,$ , $\enspace e^x<2\cosh x\,$ .