¿Estoy simplificando adecuadamente esta progresión geométrica?

Question

Estoy estudiando relaciones de recurrencia y estoy dado:

$T(n) = 2 \cdot T(n-1) - 1$

con una condición inicial que $T(1) = 3$.

He trabajado a través de los primeros recurrencias:

$T(n-1) = 2^2 \cdot T(n-2) - 2 - 1$

$T(n-2) = 2^3 \cdot T(n-3) - 2^2 - 2 - 1$

y así sucesivamente, y llegó a la conclusión de que el patrón de

$2^k \cdot T(n-k) - 2^{k-1} - 2^{k-2} - ... 2 - 1$

representa esta relación. Ya tenemos T(1) = 3, debe haber alguna $n$ e $k$ tal que $n-k = 1$, lo $k= n - 1$. Sustituyendo:

$2^{n-1} \cdot T(1) - 2^{n-2} - 2^{n-3} - ... 2 - 1$

pero T(1) = 3, así que...

$2^{n-1} \cdot 3 - 2^{n-2} - 2^{n-3} - ... 2 - 1$

Factorización de un $-1$ tengo algo que se ve por todo el mundo como una progresión geométrica:

$2^{n-1} \cdot 3 - (1 + 2 + ... + 2^{n-3} + 2^{n-2})$

Sin embargo, estoy convencido de que mi progresión de la falta de un término, es decir, $2^{n-1}$. Es fuera de la progresión, que se multiplica por tres. En mis notas, mi instructor simplificado de la progresión:

$\frac{2^{n-1} - 1}{2 - 1}$

Estoy confundido acerca de dónde se $n-1$ en el exponente de la progresión geométrica de la simplificación. Yo finalmente resolver la relación de recurrencia :

$3 \cdot 2^{n-1} - 2^{n-1} + 1 = 2^n + 1$

Es mi entendimiento de la simplificación de la progresión geométrica correcta?

Answer 1

Has conseguido una respuesta a su pregunta, pero quiero explicar cómo correctamente resolver la cuestión en un matemáticamente riguroso manera, y no apelando a handwaving. (Cada aparición de "···" es un ejemplo de falta de rigor.)

---

De trabajo 1

$T(n) - 2·T(n-1) = -1$.

$2 · ( T(n-1) - 2·T(n-2) ) = 2·-1$. // Hacemos esto para que coincida y cancelar la $2·T(n-1)$.

$4 · ( T(n-2) - 2·T(n-3) ) = 4·-1$. // Hacemos esto para que coincida y cancelar la $4·T(n-2)$.

... // No riguroso. Necesitamos expresar el patrón de rigor.

Solución 1

Tomar cualquier entero $n > 1$.

$T(n) - 2·T(n-1) = -1$.

$2^k · ( T(n-k) - 2·T(n-k-1) ) = -2^k$ para cada entero $k < n-1$.

$\sum_{k=0}^{n-2} ( 2^k · ( T(n-k) - 2·T(n-k-1) ) ) = \sum_{k=0}^{n-2} -2^k$.

$\sum_{k=0}^{n-2} ( 2^k·T(n-k) - 2^{k+1}·T(n-k-1) ) = \sum_{k=0}^{n-2} -2^k$.

$\sum_{k=0}^{n-2} (2^k·T(n-k)) - \sum_{k=0}^{n-2} (2^{k+1}·T(n-k-1)) = -2^{n-1} + 1$.

$\sum_{k=0}^{n-2} (2^k·T(n-k)) - \sum_{k=1}^{n-1} (2^k·T(n-k)) = -2^{n-1} + 1$.

$2^0·T(n-0) - 2^{n-1}·T(n-(n-1)) = -2^{n-1} + 1$.

$T(n) = 2^{n-1}·T(1) - 2^{n-1} + 1 = 2^n + 1$.

Compruebe que $T(1) = 2^1 + 1$ así, porque el anterior prueba asumido $n > 1$.

---

Solución 2

Tomar cualquier entero $n > 1$.

$T(n) - 2·T(n-1) = -1$.

$( T(n) - 2·T(n-1) ) / 2^n = -1/2^n$.

$T(n)/2^n - T(n-1)/2^{n-1} = -1/2^n$.

Tomar cualquier entero $m > 1$.

$\sum_{n=2}^m ( T(n)/2^n - T(n-1)/2^{n-1} ) = \sum_{n=2}^m -1/2^n$.

$\sum_{n=2}^m (T(n)/2^n) - \sum_{n=2}^m (T(n-1)/2^{n-1}) = -1/2 + 1/2^m$.

$\sum_{n=2}^m (T(n)/2^n) - \sum_{n=1}^{m-1} (T(n)/2^n) = -1/2 + 1/2^m$.

$T(m)/2^m - T(1)/2^1 = -1/2 + 1/2^m$.

$T(m) = 2^m·(T(1)/2-1/2) + 1 = 2^m + 1$.

Compruebe que $T(1) = 2^1+1$ así.

Answer 2

A la izquierda de la segunda y tercera ecuaciones deben ser $T(n)$, no lo que usted ha escrito. En virtud de "Factoring una $-1$" sería mejor para acabar con $2^{n-3}+2^{n-2}$ para mantener el patrón de los exponentes creciente por $1$. Su progresión no terminan con $2^{n-2}$. Es por eso que el numerador de la suma ha $2^{n-1}$. Si usted mira la fórmula para la suma de una progresión geométrica finita, el exponente es $1$ más que la más alta plazo: $$1+r+r^2+\ldots +r^k=\frac {r^{k+1}-1}{r-1}$$ Cuando se agrega $1$ a $n-2$ obtener $n-1$ así que tu profesor de la suma de la progresión es el correcto. Tu respuesta final es también correcta.

Answer 3

Si usted no está seguro de que su cálculo es correcto usted debe tratar de verificar sus cálculos.

Los primeros diez números de la primera recurrencia de la relación

$$T(n) = 2*T(n-1) - 1$$

son

$$3,5,9,17,33,65,129,257,513,1025$$

diez números de la segunda relación de recurrencia

$$T(n-1) = 2^2*T(n-2) - 2 - 1$$

son

$$3,9,33,129,513,2049,8193,32769,131073,524289$$

Así que estos son los diferentes cálculos, así que algo salió mal.

---

La frase "el patrón ... representa esta relación" es bastante claro. Darle un significado preciso y tratar de verificarla.