Resolver

Question

Mi clase y yo fuimos introducidos a una recurrencia de la semana pasada, y nos llevó hasta este ejemplo (ver enlace) en la clase. Por desgracia creo que es realmente difícil todavía, y pido disculpas si esta pregunta es...patético(?)

A partir de los pasos que se muestran clase, la solución comienza con la búsqueda de un patrón:

T(n) = 2T(n-1) + 1

=2[2T(n-2) + 1] + 1

=4[2T(n-3) + 1] + 3

=8[2T(n-4) + 1] + 7

Yo (creo yo) entender por qué 2T(n-1) + 1 está dentro de los corchetes. Pero no tengo idea de donde los 2, 4, 8, en el comienzo de cada uno) viene, como con el 1, 3, 7 y los extremos.

Cualquiera podría ser un ahorrador de vida para arrojar algo de luz sobre esto, así que puedo continuar con la práctica y la solución de otros recurrencias.

Answer 1

Lo que ocurre aquí es que la relación de recurrencia se aplica repetidamente.

Comenzaremos, para algunos $n$, con el hecho de que $$\etiqueta{1} T(n)=2T(n-1)+1. $$ Pero, sabemos que el $T(n-1)=2T(n-2)+1$; conectando a $(1)$ rendimientos $$\etiqueta{2} T(n)=2(2T(n-2)+1)+1=2^2T(n-2)+2+1. $$ Pero, sabemos que el $T(n-2)=2T(n-3)+1$; conectando a $(2)$ rendimientos $$\etiqueta{3} T(n)=2^2(2T(n-3)+1)+2+1=2^3T(n-3)+2^2+2+1. $$ Vamos a hacer uno más: sabemos que $T(n-3)=2T(n-4)+1$, por lo que $$ T(n)=2^3(2T(n-4)+1)+2^2+2+1=2^4T(n-4)+2^3+2^2+2+1. $$ Ves un patrón? Ciertamente se ve igual a la de cualquier $k<n$, tenemos $$ T(n)=2^kT(n-k)+(2^{k-1}+2^{k-2}+\cdots+2+1). $$ SI esta expresión es verdadera, entonces, en especial los de $k=n-1$ rendimientos $$ \begin{align*} T(n)&=2^{n-1}T(n-(n-1))+(2^{n-2}+2^{n-3}+\cdots+2+1)\\ &=2^{n-1}T(1)+(2^{n-2}+2^{n-3}+\cdots+2+1)\\ &=2^{n-1}+2^{n-2}+2^{n-3}+\cdots+2+1, \end{align*} $$ debido a $T(1)=1$, por definición. Ahora, este es un geométrica de la suma y puede ser simplificado a dar un bonito, de forma cerrada fórmula para $T(n)$.

Answer 2

$$T(n)=2T(n-1)+1\iff T(n)+1=2[T(n-1)+1]$$

Set $\displaystyle T(n)+1=U(n)\implies U(n)=2U(n-1)$ $U(1)=\cdots$

$\displaystyle\implies U(n)=2^rU(n-r) $ $1\le r<n$

Answer 3

Se podría haber ayudado a si que habían mostrado algunos pasos intermedios:

$$\begin{align} T(n)&=2T(n-1)+1\\ &=2[2T(n-2)+1]+1\\ &=4T(n-2)+3\quad\text{(intermediate step)}\\ &=4[2T(n-3)+1]+3\\ &=8T(n-3)+7\quad\text{(intermediate step)}\\ &=8[2T(n-4)+1]+7\\ &=16T(n-4)+15\quad\text{(intermediate step)}\\ &\vdots \end{align}$$

Cada paso intermedio sólo se expande y se recoge lo que está en la línea de arriba.