Demostrando la desigualdad...

Question

Pregunta:

$$ f(a,b)= \begin{cases} ja & \text{if } b \le 2 \\ jb & \text{if } a \le 2 \\ jab + f(d, \frac{b}{2}) + f(a-d, \frac{b}{2}) & \text{if } a,b >2\end{casos} $$ where $\ j$ is a positive constant and $ \ 1 \le d<$.

Demostrar el uso de algún tipo de inducción que $f(a,b) = \Theta(ab)$ o $ f(a,b) = \Theta(a^2b^2)$. Sólo una es correcta.

Mi intento:

Creo que el $ f(a,b) = \Theta(ab)$. Primero tenemos que demostrar que $ f(a,b) = O(ab)$$ \ f(a,b) = \Omega(ab)$.

Demostrar $ \ f(a,b) = O(ab)$:

Debemos mostrar que existen constantes positivas $c$ $ n_0$ tal que $ \ f(a,b) \le cab$$a,b \ge n_0$.

Los casos de Base:

$a=1$: $f(a,b) = jb$ por definición. Si dejamos $a=b$$jb \le cb^2$.

$b=1$: $f(a,b) = ja$ por definición. Si dejamos $a=b$$ja \le ca^2$.

$a=2$: $f(a,b) = jb$ por definición. Si dejamos $a=b$$jb \le cb^2$.

$b=2$: $f(a,b) = ja$ por definición. Si dejamos $a=b$$ja \le ca^2$.

No entiendo cómo hacer el paso de inducción. ¿Qué debería asumir en mi hipótesis de inducción y cómo debo completar la prueba?

Answer 1

Suponemos que el dominio de $f$ es un conjunto $\Bbb R^2_+$ de los pares de $(a,b)$ de los negativos de los números reales y la tercera fila de la definición significa que existe $d$ de manera tal que la demanda se mantiene. La observación de que $f(a,b)=O(ab)$ falla, por ejemplo, en la secuencia de $a_n=\frac 1n$$b_n=n^2$, debido a que, a continuación,$a_nb_n=n$, mientras que el $f(a_n,b_n)=jn^2$. Por lo que el problema de la conclusión, que debe ser corregido.

Utilizamos la inducción por $n$ que $\left(2-\frac 3{2^{n}}\right)jab-3jb\le f(a,b)\le \left(2-\frac 3{2^{n}}\right)jab+ja+jb$ donde $n$ es el menor entero positivo tal que $b\le 2^n$. Para $n=1$ esto se deduce de la definición de $f$. Supongamos que ya hemos probado que la desigualdad de la $n\ge 1$ y asumir que $2^{n}<b\le 2^{n+1}$. A continuación, $n$ es el menor número positivo tal que $\frac b2\le 2^n$. Si $a\le 2$ $f(a,b)=jb$ y es fácil comprobar que la desigualdad se cumple. Si $a>2$, a continuación, por la suposición inductiva

$$f(a,b)=jab + f\left(d, \frac{b}{2}\right) + f\left(a-d, \frac{b}{2}\right)\ge $$ $$jab + \left(2-\frac 3{2^{n}}\right)jd\frac{b}{2} + \left(2-\frac 3{2^{n}}\right)j(a-d)\frac{b}{2}-3j\frac{b}{2}-3j\frac{b}{2} =$$ $$\left(2-\frac 3{2^{n+1}}\right)jab-3jb.$$

$$f(a,b)=jab + f\left(d, \frac{b}{2}\right) + f\left(a-d, \frac{b}{2}\right)\le $$ $$jab + \left(2-\frac 3{2^{n}}\right)jd\frac{b}{2} + \left(2-\frac 3{2^{n}}\right)j(a-d)\frac{b}{2}+jd+j\frac{b}{2}+j(a-d)+j\frac{b}{2}=$$ $$\left(2-\frac 3{2^{n+1}}\right)jab+ja+jb.$$

Answer 2

a los niños. https://MCS.UTM.utoronto.CA/~236/PS/PS3.pdf

Por favor no engañar. No deseando perseguir delitos académicos sobre este.