Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Prove a seguinte identidade: \[ \left( \frac{a}{b^k} \right)^{log_{b}n} = \frac{n^{log_{b}a}}{n^k} \]

0 votos
24 visitas
perguntada Ago 6 em Matemática por VITOR B BORGES (1 ponto)  
editado Ago 23 por VITOR B BORGES

A pergunta corresponde ao exercício 3.1 localizado na página 101 na seção 4 do Capítulo 3 do livro "Runtime Analysis of Recursive Algorithms" de Manuel Rubio-Sánchez.

Compartilhe

1 Resposta

0 votos
respondida Ago 6 por VITOR B BORGES (1 ponto)  

Para provar esta identidade iremos partir da expressão inicial \( \left( \frac{a}{b^k} \right)^{log_{b}n} \), e ir manipulando usando identidades algébricas conhecidas, até ela ficar igual à expressão desejada \( \frac{n^{log_{b}a}}{n^k} \).

As identidades conhecidas que usaremos são:

\( 1. \hspace{0.2cm} \alpha \cdot \log_{\beta}n = \log_{\beta}n^\alpha \),

\( 2. \hspace{0.2cm} \alpha^{\log_{\alpha}n} = n \) ,

\( 3. \hspace{0.2cm} \log_{\alpha}\alpha = 1 \) ,

e a mudança de base do logarítmo:

\( 4. \hspace{0.2cm} \log_{\alpha}n = \frac{\log_{\beta}n}{\log_{\beta}\alpha} \) .

Começaremos descendo o expoente da primeira expressão para ficar com,

\[ \left( \frac{a}{b^k} \right)^{log_{b}n} = \frac{a^{log_{b}n}}{b^{k \cdot log_{b}n}}, \]

Onde invocamos a identidade de numero 1. citada,

\[ \frac{a^{log_{b}n}}{b^{k \cdot log_{b}n}} = \frac{a^{log_{b}n}}{b^{log_{b}n^k}} \]

Como chegamos em "b" elevado à log de base "b", usamos à identidade 2. que resulta em,

\[ \frac{a^{log_{b}n}}{b^{log_{b}n^k}} = \frac{a^{log_{b}n}}{n^k} \]

Agora o nosso denominador se encontra igual ao da expressão dejada, partamos então para a simplificação do númerador, para isso iremos invocar pela primeira vez a identidade 4. a mudança de base do logarítmo. Note que,

\[ \frac{a^{log_{b}n}}{n^k} = \frac{a^{\left( \frac{log_{a}n}{log_{a}b} \right)}}{n^k} = \frac{a^{\left( log_{a}n \right) \cdot \left( 1/log_{a}b \right)}}{n^k} = \frac{\left( a^{log_{a}n} \right)^{(log_{a}b)^{-1}}}{n^k}, \]

Onde invocamos mais uma vez a identidade 2. que resulta em,

\[ \frac{n^{(log_{a}b)^{-1}}}{n^k} \]

Usando pela segunda vez a mudança de bases, podemos concluir que,

\[ \frac{n^{\left( \frac{log_{b}b}{log_{b}a} \right)^{-1}}}{n^k} = \frac{n^{\left( \frac{log_{b}a}{log_{b}b} \right)}}{n^k} \]

Onde chamamos a última identidade que será usada, a de número 3,

\[ \frac{n^{\left( \frac{log_{b}a}{1} \right)}}{n^k} = \frac{n^{log_{b}a}}{n^k} \]

, nossa expressão final.

\[ CONCLUSÃO: \left( \frac{a}{b^k} \right)^{log_{b}n} = \frac{n^{log_{b}a}}{n^k} \]

...