Pregunta sobre ecuaciones y algoritmos

Question

Esta pregunta es sobre matemáticas discretas. Necesito verificar si esta ecuación es correcta:

$\sum_{i = 1}^{n} 7^i log_2 (i) = \Theta(7^n log_2 (n))$

¿Cómo puedo demostrar eso? Soy nuevo en esto, así que lamento si hice algo mal en esta pregunta. Estoy teniendo muchas dificultades con esta en particular y no tengo idea de por dónde empezar. Tengo que recurrir a esto porque no puedo obtener una respuesta de mi profesor.

Answer 1

Primero que nada, $\log_2 i$ siempre es menor que $\log_2 n$ en tu suma. Así que tienes: $$ \sum_{i=1}^n 7^i \log_2 i \leq \log_2 n \sum_{i=1}^n 7^i $$ Luego, utilizando la suma de términos de una serie geométrica, obtienes $$ \sum_{i=1}^n 7^i \log_2 i \leq \log_2 n \left(\frac{7^{n+1} - 7}{6}\right). $$ Esto es suficiente para mostrar que tu suma es un $\mathcal{O}\left(\log_2 n 7^n\right)$. Ahora solo tienes que encontrar una cota inferior correspondiente. ¡Espero que eso ayude...

Answer 2

Es suficiente investigar $$S_n:=\sum_{k=1}^n 7^k\log k.$$ Ahora divídalo en dos partes : $$S_n=\sum_{k=1}^{n-\lfloor\log n\rfloor}+\sum_{k=n-\lfloor\log n\rfloor+1}^n=S_n^1+S_n^2.$$ Es trivial que $$S_n^1\leqslant 7^{n+2-\log n}\log n=\mathcal{O}\left(\frac{7^n\log n}{n^{\log 7}}\right).$$ Por otro lado, \begin{align*} S_n^2& =\sum_{k=1}^{\lfloor\log n\rfloor}7^{n+1-k}\log(n+1-k)\\ & =7^{n+1}\sum_{k=1}^{\lfloor\log n\rfloor}\frac{\log(n+1)+o(1)}{7^k}\\ & =\frac{1}{6}\cdot 7^{n+1}\log n(1+o(1)). \end{align*} Por lo tanto $S_n=\frac{1}{6}\cdot 7^{n+1}\log n(1+o(1)).$

Luego, cuando $n\to \infty$, $$\sum_{k=1}^n 7^k\log_2 k\sim\frac{7^{n+1}\log n}{6\log 2}.$$