Olimpíadas

Para [tex3]n∈ℕ[/tex3] , mostre que: [tex3]\sum_{k=0}^{n} \frac{n!}{(n-k)!}=⌊n!e⌋[/tex3] , onde [tex3]⌊x⌋[/tex3] representa o maior inteiro menor ou igual a x e [tex3]e=2,718\dots .[/tex3]

Resposta

Demonstração

Corrigindo Possível Erro

Quando eu estava acabando de escrever a resposta, encontrei um erro. A questão proposta não vale para [tex3]n=1[/tex3] , pois resulta em [tex3]1=2[/tex3] , também teste para [tex3]n=2[/tex3] e resultou em [tex3]4=5[/tex3] , imagino que o erro veio sobre a definição de [tex3]k=1[/tex3] , creio que deveria ser [tex3]k=0[/tex3] . Isso corrige para todos os casos, então apenas mudei os valores nas contas e vou seguir usando isso, afinal, "eu já quase terminei de escrever tudo kkkkk".

Permutação Caótica

Esse exercício me lembra muito a Demonstração da Permutação Caótica. Parece ser uma simplificação dele. Em Permutação Caótica temos a simplificação:

[tex3]n!\sum_{i=0}^{n}\frac{(-1)^i}{i!}\approx\frac{n!}{e}[/tex3]

A ideia em si é bem semelhante.

Simplificando o Somatório

Agora, destrinchando a equação proposta:
[tex3]\sum_{k=0}^{n} \frac{n!}{(n-k)!}=n!\sum_{k=0}^{n} \frac{1}{(n-k)!}[/tex3]

Vamos aplicar uma mudança de variável, na qual [tex3]\boxed{i=n-k\,\,\,\therefore \,\,\,k=n-i}[/tex3]
[tex3]n!\sum_{{\color{SeaGreen}k}\,=\,0}^{n} \frac{1}{({\color{Purple}n-k})!}=n!\sum_{{\color{SeaGreen}n-i}\,=\,0}^{n} \frac{1}{{\color{Purple}i}!}[/tex3]

E podemos adicionar uma correção de variável
[tex3]n!\sum_{{\color{Magenta}n-i=0}}^{\color{Magenta}n} \frac{1}{i!}=n!\sum_{{\color{Magenta}i=0}}^{\color{Magenta}n} \frac{1}{i!}[/tex3]

[tex3]\boxed{\sum_{k=0}^{n} \frac{n!}{(n-k)!}=n!\sum_{{i=0}}^{n} \frac{1}{i!}}[/tex3]

Assumindo [tex3]e[/tex3] e Testando Valores

Mantenha em mente que:

[tex3]e=\sum_{i=0}^\infty\frac{1}{i!}[/tex3]

Note que [tex3]\sum_{i=0}^{n} \frac{1}{i!}[/tex3] é um Somatório Limitado para o número de Euler. No mais, quanto maior for [tex3]n[/tex3] , menor é a fração [tex3]+\frac{1}{n}[/tex3] , ou seja, menor é a adição ao resto do somatório. então, podemos usar esse somatório para uma aproximação de [tex3]e[/tex3] e que quanto maior [tex3]n[/tex3] , mais próximo o somatório se torna de [tex3]e[/tex3]

Para validar essa afirmação, temos que verificar os primeiros valores para nos certificar que no início, quando [tex3]\frac{1}{n}[/tex3] tem mais impacto no somatório.

[tex3]n=1[/tex3]
[tex3]{\color{Blue}1}!\sum_{{i=0}}^{\color{Blue}1} \frac{1}{i!}=\frac{1}{0!}+\frac{1}{1!}=2\\\left\lfloor{\color{Blue}1!}\cdot e\right\rfloor=\left\lfloor2,\!718...\right\rfloor =2 [/tex3]

[tex3]n=2[/tex3]
[tex3]{\color{Blue}2}!\sum_{{i=0}}^{\color{Blue}2} \frac{1}{i!}=2\cdot\[\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}\]=5\\\left\lfloor{\color{Blue}2!}\cdot e\right\rfloor=\left\lfloor5,\!436...\right\rfloor =5 [/tex3]

[tex3]n=3[/tex3]
[tex3]{\color{Blue}3}!\sum_{{i=0}}^{\color{Blue}3} \frac{1}{i!}=6\cdot\[\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\frac{1}{3!}\]=16\\\left\lfloor{\color{Blue}3!}\cdot e\right\rfloor=\left\lfloor16,\!308...\right\rfloor =16 [/tex3]

Note também intuitivamente que a diferença diminui conforme [tex3]n[/tex3] aumenta.

Sobre o Erro em Si

Quando eu terminei as mudanças, cheguei em:

[tex3]\sum_{k=0}^{n} \frac{n!}{(n-k)!}=n!\sum_{{i=0}}^{n-1} \frac{1}{i!}[/tex3]

E esse [tex3]\boxed{n-1}[/tex3] começou a falhar minhas contas quando estava testando os valores quando escrevia a última parte (aqui é assim, vai fazendo a conta e escrevendo a resposta. Legal é quando vê que fiz algo muito errado que me obriga a recomeçar :v), então comecei a testar os valores para a equação inicial proposta no exercício e notei que os próprios valores no iniciais não estavam batendo.

LostWalker, o livro diz k=0, foi erro meu. Me desculpe.

⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀

[tex3]n!\sum_{i=0}^{n}\frac1{i!} = n! \cdot e - \sum_{i=n+1}^{\infty} \frac{n!}{i!}[/tex3] , agora é ver que:

[tex3]\sum_{i=1}^{\infty} \frac{n!}{(n+i)!} < 1[/tex3]

parece difícil provar essa parte

FelipeMartin, essa parte não é o suficiente?

LostWalker escreveu: ↑
Ter 02 Mar, 2021 12:20
Note que ∑i=0n1i!∑i=0n1i! é um Somatório Limitado para o número de Euler. No mais, quanto maior for nn , menor é a fração +1n+1n , ou seja, menor é a adição ao resto do somatório. então, podemos usar esse somatório para uma aproximação de ee e que quanto maior nn , mais próximo o somatório se torna de ee

Para validar essa afirmação, temos que verificar os primeiros valores para nos certificar que no início, quando 1n1n tem mais impacto no somatório.

FelipeMartin, eu entendi sim o seu ponto, mas provar

[tex3]\sum_{i=1}^{\infty} \frac{n!}{(n+i)!} < 1[/tex3] não necessariamente é determinante. Por exemplo, vamos supor, por absurdo, que

[tex3]\exists \,\,n\in\mathbb{N} \,\,\,|\,\,\sum_{i=1}^{\infty} \frac{n!}{(n+i)!}=0,999...[/tex3]

Veja que:
[tex3]n\cdot e!-0,999...[/tex3]
Já seria o suficiente para que o valor passasse para outra unidade.

Quando meu professor me ensinou a Permutação Caótica, ele abortou de forma intuitiva, mostrando que, se os primeiros valores, com maiores impactos no somatório, no caso, maior impacto por não ser tão próximos de [tex3]e[/tex3] , já se adequam na aproximação e que quanto maior [tex3]n[/tex3] , mais próximo de [tex3]e[/tex3] , ou seja, menor é a diferença, é aceitável dizer que a proposição é válida. Encontrar uma equação para prova de maneira exata que essa equação sempre se mantém constante é uma matemática mais complexa, e ao menos, eu no momento não sei.

NigrumCibum, eu acho que esse argumento não basta, pois são somados infinitos termos.

Olimpíadas ⇒ Análise Combinatória

Análise Combinatória

Re: Análise Combinatória

Re: Análise Combinatória

Re: Análise Combinatória

Re: Análise Combinatória

Re: Análise Combinatória

Re: Análise Combinatória

Re: Análise Combinatória

Olimpíadas ⇒ Análise Combinatória

Entrar • Registrar