Divisibilidade/ Princípio da Indução Finita

por BEKJINU Qui 26 Jan 2023, 11:24

Mostre que para todo n≥3, n! pode ser escrito como a soma de n divisores distintos dele mesmo.

por JaquesFranco Qui 26 Jan 2023, 18:14

Para n = 3:
3! = 1 + 2 + 3.

Passo indutivo:
Suponha que [latex]n! = x_1 + x_2 + x_3 + ... + x_k[/latex], no qual [latex]x_y[/latex] é divisor de [latex]n![/latex] com [latex]1 \leq y \leq k[/latex].

Note que
[latex](n + 1)! = (n+1)(n!) = (x_1 + x_2 + x_3 + ... + x_k)(n + 1) = x_1(n+1) + x_2(n+1) + x_3(n+1) + ... + x_k(n+1)\ (i)[/latex]

Perceba que se [latex]x_y \mid n! \Rightarrow x_y(n+1) \mid n!(n+1) \Rightarrow x_y(n+1) \mid (n+1)![/latex]

Logo todos as parcelas de (i) dividem [latex](n+1)![/latex]

por BEKJINU Qui 26 Jan 2023, 20:43

Obrigado!

por **Matheus Tsilva** Sex 27 Jan 2023, 07:50

Jaques, parabéns pela resolução, mas só para deixar bala, tenho algumas ressalvas:

- k = n

- perceba que o enunciado pede n divisores para n!, para (n+1)! na indução você mostrou que tem k = n, o certo seria ter n+1, daí seria só acrescentar o 1.

por BEKJINU Sex 27 Jan 2023, 08:07

Matheus Tsilva escreveu:Jaques, parabéns pela resolução, mas só para deixar bala, tenho algumas ressalvas:

- k = n

- perceba que o enunciado pede n divisores para n!, para (n+1)! na indução você mostrou que tem k = n, o certo seria ter n+1, daí seria só acrescentar o 1.

Matheus, n entendi sua segunda afirmação. Ele substituiu o n! pela soma dos k=n divisores dele, que mostrou na hipótese. N entendi pq adicionar o [latex]^{x_{k+1}}[/latex].

por **Matheus Tsilva** Sex 27 Jan 2023, 08:14

Sim, mostrou, a solução dele está toda certa

Mas o enunciado pede para demonstrar que n! pode ser escrito como a soma de n divisores diferentes, correto ?

Então (n+1)! tem que ser escrito como a soma de (n+1) divisores diferentes, se você perceber ele colocou apenas n divisores diferentes, entendeu ?

Foi um pequeno detalhe apenas

por BEKJINU Sex 27 Jan 2023, 08:24

Matheus Tsilva escreveu:Sim, mostrou, a solução dele está toda certa

Mas o enunciado pede para demonstrar que n! pode ser escrito como a soma de n divisores diferentes, correto ?

Então (n+1)! tem que ser escrito como a soma de (n+1) divisores diferentes, se você perceber ele colocou apenas n divisores diferentes, entendeu ?

Foi um pequeno detalhe apenas

Ahh ss, entendi. Mas como eu adicionaria esse termo e mostraria que ele divide (n+1)! ? Pq simplesmente adicionar o [latex]x_{n+1}[/latex] na soma não prova que ele divide o (n+1)!, certo?

por **Matheus Tsilva** Sex 27 Jan 2023, 08:56

Eu achei que era mais simples e dava para colocar algum fator na resolução do amigo Jaques, mas não encontrei

consegui pensar nisso aqui, alterando algumas coisas

para n = 3 ---> Jaques

para n = k supondo verdade:

k! = x1 + x2 + x3 + ... + xk

para n = k + 1

x1 + x2 + ... + xk = k!

somando dos dois lados y = k!(k), teremos:

x1 + x2 + ... + xk + k!(k) = k! + (k).k!

xk é divisor de k!, logo xk é necessariamente menor ou igual a k!. Portanto,

x1 + x2 + ... + xk + k!.(k) = k!(k+1)

x1 + x2 + ... + xk + k!.(k) = (k+1)!

Provando a indução para o caso do próximo.

por JaquesFranco Sex 27 Jan 2023, 09:14

Matheus Tsilva escreveu:Eu achei que era mais simples e dava para colocar algum fator na resolução do amigo Jaques, mas não encontrei

consegui pensar nisso aqui, alterando algumas coisas

para n = 3 ---> Jaques

para n = k supondo verdade:

k! = x1 + x2 + x3 + ... + xk

para n = k + 1

x1 + x2 + ... + xk = k!

somando dos dois lados y = k!(k), teremos:

x1 + x2 + ... + xk + k!(k) = k! + (k).k!

xk é divisor de k!, logo xk é necessariamente menor ou igual a k!. Portanto,

x1 + x2 + ... + xk + k!.(k) = k!(k+1)

x1 + x2 + ... + xk + k!.(k) = (k+1)!

Provando a indução para o caso do próximo.

Bom dia Matheus, também achei que o problema era mais simples, o problema é que k!(k) não é divisor de (k+1)!, perceba que se:
k!(k) | (k+1)k! então k deve dividir (k + 1), o que é um absurdo.
Acho que deve ter alguma saída por indução forte, algo assim.

por JaquesFranco Sex 27 Jan 2023, 09:36

Da pra fazer algo assim, e provar que sempre é possível.

3! = 1 + 2 + 3
4! = 4 + 8 + 12 = 1 + 3 + 8 + 12
5! = 5 + 15 + 40 + 60 = 1 + 4 + 15 + 40 + 60