Re: [obm-l] Indução Finita

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

Title: Re: [obm-l] Indução Finita

on 27.04.03 10:53, André Luíz at conectado2002@ieg.com.br wrote:

> Oi amigos, gostaria que vocês me ajudasse nessas três questões de indução:
>  
> 1) Para n >= 3 mostre que (n+1)^n < n^(n+1)
>  
> 2) Para n >= 2 mostre que 1 * 3 * 5 * ..... * (2n - 1) < n^n
>  
> 3) Mostre que é possível pagar, sem receber troco, qualquer quantia inteira de reais, maior do que 7, com notas de 3 reais e 5 reais.
>  
> 4) Para n >= 3, mostre que 2^n + 1 é um número composto se n não é uma potência de 2.
>  
> Desde já muito obrigado.

O no. 4 pode ser feito sem inducao.

Suponha que n nao seja uma potencia de 2. 
Seja p o maior divisor impar de n. 
Como n >= 3, temos que p >= 3, e podemos escrever n = (2^k)*p, onde k eh um inteiro nao negativo.

Seja a = 2^k
2^n + 1 = 2^((2^k)*p) + 1 = a^p + 1 =
= (a + 1)*(a^(p-1) + a^(p-2) + ... + a + 1).

Como a >= 1 e p >= 3, ambos os fatores sao >= 2. Logo, 2^n + 1 eh composto.

Um abraco,
Claudio.