Seja
f(x) = { 0 se x = 1, 2 * f(⌊x / 2⌋) + x se x > 1 }
uma função definida nos inteiros positivos, onde ⌊x/2⌋ é o número x / 2 arredondado para baixo. Prove que f(x) <= x * log2(x) para todo inteiro x ≥ 1.

Passo 1

Primeiro, vamos entender o que a questão está pedindo. Temos uma função definida para números inteiros positivos:
Nosso objetivo é provar que para todo inteiro , . Para isso, vamos usar princípios de recorrência e propriedades dos logaritmos.

Passo 2

Vamos começar observando o caso base, ou seja, quando .
Quando :
E queremos verificar se:
Sabemos que , então:
Isso é verdade, então o caso base está confirmado.

Passo 3

Agora, assumimos que a afirmação é verdadeira para algum inteiro , ou seja, assumimos que:
Esse é o nosso passo de indução. Agora, precisamos mostrar que isso implica que a afirmação também é verdadeira para , ou seja:

Passo 4

Vamos analisar :
Dependendo se é par ou ímpar, será ou . Mas, para simplificar, vamos considerar que é , onde .
Pelo passo de indução:

Passo 5

Substituindo essa desigualdade na expressão de :
Sabemos que , então:
Simplificando:

Passo 6

Agora, utilizamos a propriedade dos logaritmos que diz . Substituindo:
Distribuindo:
Os termos e se cancelam:

Resposta

Assim, mostramos que se , então . Pelo princípio da indução matemática, concluímos que para todo inteiro , .

Exercícios relacionados

11-30= Calcule o limite, se existir.
21. lim t 4 9-t3-raizt
Seja x um inteiro maior do que um. Prove que, se x não é divisível por nenhum número primo menor ou igual à sua raiz quadrada, então x é primo.
Prove que não existe o menor número real positivo.
Calcule: (3 - 4i) / (2 - 5i)