Haga clic para solventar la ecuación con la configuración actual.

Question

Pregunta: Dada la ecuación de recurrencia para la secuencia de Fibonacci recursivo programa:

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

$T(0) = T(1) = a$

El uso de la inducción, muestran que $T(n) \leq f(n)$ donde $f(n) = c2^n, \forall n \geq 0$. Encontrar un valor de $c$ en el proceso.

Intento de Solución:

Caso Base para n=0: $f(0) = c$, por lo que tiene la restricción $a \leq c$

Caso Base para n=1: $f(1) = 2c$, por lo que tiene la restricción $a \leq 2c$

Inductivo paso:

• $T(n) = T(n-1) + T(n-2) + b$
• $T(n+1) = T(n) + T(n-1) + b$
• $T(n+1) = c2^n + c2^{n-1} + b$

No estoy muy seguro de dónde ir después de esto, tampoco estoy muy seguro de si lo que hemos hecho hasta ahora es de ningún valor en absoluto.

Answer 1

Calcular. Tenemos $T(2)=2a+b$, $T(3)=3a+2b$, $T(4)=5a+4b$, $T(5)=8a+7b$, $T(6)=13a+12b$, y así sucesivamente. Los coeficientes de crecimiento rápido, pero no demasiado rápido.

Por simplicidad, suponga que $a$ $b$ son no-negativos.

Se demuestra por inducción que $T(n)\le 2^n a+2^n b=(a+b)2^n$. Para la inducción de paso, supongamos que $T(k-1)\le 2^{k-1}(a+b)$$T(k-2)\le 2^{k-2}(a+b)$. Tenemos que mostrar que $T(k)\le 2^k(a+b)$.

Para ello es suficiente para demostrar que $2^{k-1}+2^{k-2}+1\le 2^k$. Esto no es difícil, ya que $1+2+\cdots +2^{k-1}=2^k-1$.

Detalle: Vamos A $c=a+b$. Deje $A(n)$ ser la afirmación de que $T(n)\le (a+b)2^n$ e$T(n+1)\le (a+b)2^{n+1}$. It is clear that $a(0)$ holds. We show that if $A(k)$ holds, then $A(k+1)$ holds. So we need to show that $T(k+1)\le (a+b)2^{k+1}$ and $T(k+2)\le (a+b)2^{k+2}$.

Está construido en $A(k)$ que $T(k+1)\le (a+b)2^{k+1}$. Por lo que es suficiente para mostrar que el $T(k+2)\le (a+b)2^{k+2}$.

Tenemos $T(k+2)=T(k+1)+T(k)+b$. Por la hipótesis de inducción, $T(k+1)\le (a+b)2^{k+1}$$T(k)\le (a+b)2^k$. Así $$T(k+2)\le (a+b)2^{k+1}+(a+b)2^k +b\le (a+b)2^{k+1}+(a+b)2^k +a+b.\tag{1}$$ Así, a partir de (1) obtenemos $$T(k+2)\le (a+b)(2^{k+1}+2^k+1).$$ Pero $2^{k+1}+2^k+1 \le 2^{k+2}$. De ello se desprende que $T(k+2)\le (a+b)2^{k+2}$. Esto completa el paso de inducción.