Demostrar por inducción $T(n) = 2T(\frac{n}{2}) + 2$

Question

Yo estoy atascado con esta prueba de inducción:

Hasta ahora, dado:

$\begin{align*} T(1) & = 2 \\ T(n) & = 2T(n/2)+2 \\ & = 2(2T(n/[2^2])+2) + 2 \\ & = [2^2]T(n/[2^2]) + [2^2] + 2 \\ & = [2^2](2T(n/[2^2])+2) + [2^2] + 2 \\ & = [2^3]T(n/[2^3]) + [2^3] + [2^2] + 2 \\ & = [2^3]T(n/[2^3]) + 2\{[2^2] + [2^1] + 1\} \\ & \vdots \\ & = [2^k]T(n/[2^k]) + 2\{2^{k} - 1\} \end{align*} $

Entonces, Cómo demuestro que se trata de corregir (la prueba). Hasta ahora tengo:

Que $(n/[2^k]) = 1$

$\Rightarrow n = 2^k$

Así, $T(n) = nT(1) + 2(n - 1)$

$T(n) = 4n - 2$ //This es que estoy atrapado.

De la prueba (por inducción):

Cuando $n = 1$, $T(1) = 2$.

$T(k)$ Es verdadero [$T(n) = 4n - 2$] //This es que estoy atrapado.

Answer 1

Sugerencia $\: $ de los primeros valores algunos adivinamos $\rm\ T(2^n)\ =\ 2^{n+2}-2\ $ y la inducción lo confirma:

$$\rm T(2^{n+1})\ =\ 2\ T(2^n) + 2 \ =\ 2\ (2^{n+2}-2) +\ 2\ =\ 2^{n+3} - 2$$

Uno puede extender $\rm\:T\:$ $\:\mathbb N\:$ mediante la definición de $\rm\ T(2k+1) = 2\ T(k+1)-2 $ y ahora uno fácilmente prueba por inducción que $\rm\ T(k) = 4\:k-2\ $ desde

$\rm\quad\quad\quad\quad\quad\quad\quad T(2k+1)\ =\ 2\ T(k+1)-2\ =\ 2\ (4k+2)-2\ =\ 4(2k+1)-2 $

$\rm\quad\quad\quad\quad\quad\quad\quad\quad\quad\ T(2k)\ =\ 2\ \ \ \ T(k)\ \ +\ \ \: 2\ =\ 2\ (4k-2) + 2\ =\ 4 (2k) - 2 $

Answer 2

Si calculas $T(n)$ se puede observar que $T(n)=4n-2$. Para demostrar por inducción, observe que es verdad $n=1$ $T(1)=2=4*1-2$. Entonces es verdad $T(n)$ y demostrar que es verdad $T(2n)$.

Answer 3

Aquí es cómo este intento desde el punto que te quedaste:

Sabemos que $\rm T(1) = 2$. Estamos tratando de probar que $\rm T(n) = 4n-2$.

Esto es trivial verdad $n = 1$:

$ \rm\begin{eqnarray*} T(1) &=& 4(1) - 2\\ &=& 4 - 2\\ &=& 2 \\ \end{eqnarray *} $

Asumir

$\rm T(k) = 4k - 2 $

De la definición original:

$\rm T(k+1) = 2T( [k+1] / 2 ) + 2 $

desde que asumió hasta $T(k)$ es correcto y está a menos de $(k+1)/2$ $T(k)$, sustituimos:

Así pues, tenemos

$ \rm\begin{eqnarray*} &2&( 4( (k+1) /2) - 2 ) + 2 \\ &=& 4(k+1)- 4 + 2\\ &=& 4(k+1) - 2 \end{eqnarray *} $

Demostrado.