Resumo do meu curso de Matemática Discreta – Parte 2: Recorrências e Teoria das probabilidades

Essa é a parte 2 do resumo do meu curso de Matemática Discreta. Separei ele em 3 partes, uma parte pra cada prova.

Você pode conferir a parte 1 e parte 3 aqui:

Resumo do meu curso de Matemática Discreta – Parte 1: Análise Combinatória

Resumo do meu curso de Matemática Discreta – Parte 3: Teoria dos Grafos

Quase todos os dias, após as aulas, eu vinha aqui escrever o que o professor passou.

Separei o resumo em resumo e comentários. O resumo é o que está seguido de bolinhas e os comentários não.

— publicidade —

Aula 11: introdução as recorrências

• Começo do conteúdo para a P2. A aula foi sobre recorrências.

O livro do Morgado não fala sobre recorrências, então agora estou vendo mais coisas do que imaginava. Mas o assunto é bem interessante.

• Definição de recorrência como uma função da forma $x_{n+1} = f(n, x_n, x_{n-1}, … , x_1)$.

Note que as entradas da função recorrência são sequências, isso é uma formalização bem complicada de entender. Pra ser sincero eu nem entendi isso ainda.

Parece que uma recorrência também é uma sequência, pois seu domínio pode ser visto como sendo os números naturais. Daí recorrência seria uma sequência definida usando outra sequência e o teorema da recursão.

• Definição da sequência dos ímpares usando recorrência.

O professor usou esse exemplo para mostrar que apenas a fórmula recursiva não define a recorrência, pois mesmo fixando a fórmula, dependendo de quem você escolhe pra ser o $x_1$ você obtém sequências diferentes.

• Definição de uma PA usando recorrência.

• Definição de PG usando recorrência.

• Definição da sequência de Fibonacci usando recorrência.

O professor usou esse exemplo para comentar que as recorrências possuem ordem. A sequência de Fibonacci é uma recorrência de ordem 2, pois depende tanto do $x_{n-1}$ quanto do $x_{n-2}$.

• Cálculo de quantas sequências de 10 termos formadas por 0’s, 1’s e 2’s não possuem dois zeros consecutivos usando recorrência.

Eu não entendi isso direito na aula, mas entendi quando peguei pra refazer em casa. Até aqui usamos o PFC para chegar na recorrência.

• Definição de recorrência linear.

• Definição de permutação caótica, que é uma permutação (função do $I_n$ pro $I_n$ que não tem nenhum ponto fixo).

Quando um amigo meu (lá em 2023) me recomendou ler o Morgado, ele falou que parou na seção que o Morgado fala disso. Finalmente aprendi essa definição hehe.

• Cálculo de quantas permutações caóticas de $n$ elementos existem usando recorrência.

Confesso que boiei completamente quando o professor fez isso.

• Definição de fatorial usando recorrência.

• Comentário sobre o que é resolver uma recorrência.

Uma recorrência nada mais é do que uma sequência definida recursivamente. Dito isso, resolver uma recorrência significa achar uma expressão geral para o $x_n$ que esteja em função apenas do $n$ e do $x_1$.

Em outras palavras, a solução de uma recorrência é uma sequência que você sabe a fórmula do termo geral.

• Resolução de uma recorrência específica.

• Resolução de outra recorrência específica.

• Prova de que se $a_n$ é uma solução da recorrência $x_{n+1} = g(n)x_n$ então a subsituição $x_n= a_ny_n$ transforma a recorrência $x_{n+1} = g(n)x_n + h(n)$ em $y_{n+1} = y_n + \frac{h(n)}{g_n a_n}$.

Com esse teorema se torna possível resolver TODAS as recorrências de 1ª ordem, pois: para resolver recorrências da forma $x_{n+1} = f(n) x_n$ basta escrever o $x_2$ em função do $x_1$, o $x_3$ em função do $x_2$ e assim vai, ai depois você multiplica lado a lado todas as igualdades. Para resolver as recorrências do tipo $x_{n+1} = x(n) + f(n)$ basta fazer o mesmo e depois SOMAR as igualdades. E para resolver as recorrênciass do tipo $x_{n+1} = g(n)x_n + h(n)$ basta usar o teorema acima.

Note que usamos o teorema acima pra sumir com a $g(n)$ que acompanha o $x_n$. Se você tentar usar as técnicas de somar/multiplicar lado lado as igualdades para resolver esse tipo de recorrência você verá que isso não ajudará.

Novamente a substituição de variáveis sendo o melhor amigo do matemático. Ainda quero saber porque isso é permitido.

• O professor resolveu a recorrência $x_{n+1} = 2 x_n + 1$ onde $x_1 = 2$ usando o teorema acima.

Aula 12: recorrências lineares de 2ª ordem com coeficientes constantes homogênea

A aula foi sobre recorrências de 2ª ordem.

• Definição de recorrência de 2ª ordem com coeficientes constantes homogênea como sendo uma recorrência da forma $x_{n+2} + p x_{n+1} + q x_n = 0$ com $q \neq 0$.

Durante a aula eu achei que o $p$ que deveria ser diferente de zero, mas graças a uma fala do professor percebi que se fosse assim, o próximo $x_n$ só dependeria do anterior, então a recorrência seria de primeira ordem. Logo, quem deve ser diferente de zero é o $q$ mesmo.

• Definição de equação característica de uma recorrência de 2ª ordem.

• Prova de um teorema que diz que toda expressão da forma $x_n = c_1 r_1^n + c_2 r_2^n$ onde $r_1, r_2$ são soluções da equação característica da recorrência é uma solução da recorrência linear de 2ª ordem homogênea.

A prova é legal. Mas o resultado é difícil de engolir, pois é um resultado muito forte.

• Prova de que TODA solução de uma recorrência linear de 2ª odem homogênea é da forma $x_n = c_1 r_1^n + c_2 r_2^n$.

A prova parece difícil.

• Resolução de algumas recorrências usando a teoria acima. Uma delas foi a de Fibonacci.

• Generalização dos teoremas acima para os números complexos.

Eu boiei nessa parte da aula.

• Resolução da recorrência $x_{n+2} + x_{n+1} + x_n = 0$.

• O tempo todo o professor falava que esse assunto era análogo a teoria que vi em Cálculo 4 de resolver EDOs de 2ª ordem.

Essas aulas sobre recursão estão abrindo um mundo para mim, que tem a ver com Alan Turing.

— publicidade —

Aula 13: fim das recorrências lineares de 2ª ordem e começo de probabilidade

• Prova de que se as raízes da equação característica de uma recorrência de 2ª ordem homogênea são repetidas então $a_n = c_1 r^n + c_2 n r^n$ são soluções da recorrência.

A parte mais difícil é usar que $r = \frac{-p}{2}$.

• Prova de que toda solução uma recorrência de 2ª ordem homogênea com raízes repetidas é da forma $a_n = c_1 r^n + c_2 n r^n$.

A prova usa deteminante de matriz $2×2$ e é confusa.

• Resolução de $x_{n+2} – 4 x_{n+1} + 4 = 0$.

É literalmente só usar o teorema.

• Prova de que uma substituição lá transforma uma recorrência de 2ª ordem não homogênea em uma homogênea.

Por causa dessa substituição, para resolvermos uma recorrência de 2ª ordem não homogênea temos que chutar uma solução (igual em EDO).

• Resolução de $x_{n+2} – 6 x_{n+1} + 8x_n = n + 3^n$. Da trabalho pra caramba.

• Começo da parte de probabilidade.

• Definição de experimento aleatório, espaço amostral e evento.

A definição de experimento aleatório é extremamente abstrata.

Acho que quase tudo na probabilidade se resume a calcular o espaço amostral e a probabilidade de eventos.

O algorítmo para resolver todos os problemas de probabilidade é começar deduzindo o espaço amostral e calculando sua cardinalidade e depois calcular a cardinalidade do conjunto dos casos favoráveis. Essa segunda parte pode ser feita de forma indireta calculando a cardinalidade do conjunto de casos não favoráveis.

• Definição de o que é um evento ocorrer.

A parte mais difícil dos problemas de probabilidade é descobrir quem são os casos favoráveis e os casos totais pois isso são literalmente problemas de Análise Combinatória.

Calcular a cardinalidade de eventos deve ser mais díficil que calcular a cardinalidade de espaços amostrais.

• Alguns exemplos de eventos.

• Definição de probabilidade. É uma função $P$ de $\mathbb{P}(\Omega) \rightarrow [0, 1]$ que satisfaz algumas propriedades.

Segue da definição que existe mais de uma probabilidade. A função escolhida é completamente arbitrária. Você pode escolher uma probabilidade onde a chance de ao jogar uma moeda sair cara é 100%, por exemplo.

Sobre um mesmo espaço amostral é possível definir infinitas probabilidades. Por isso um fenômeno aleatório é representado por um par ordenado cujos os componentes são o espaço amostral e a função probabilidade.

A definição de probabilidade do Cardano é equiprovável. Aparentemente é mais fácil calcular probabilidades quando os eventos elementares são igualmente prováveis.

Na definição de probabilidade do Cardano não é possível calcular a probabilidade de sair um 5 num arremesso de um dado viciado.

Acho que o único espaço de probabilidade equiprovável é o que a definição de probabilidade é a do Cardano.

• Prova de que $P(\emptyset) = 0$.

• Prova de que $P(A) = \frac{|A|{|S|}$ é uma probabilidade. Temos que usar que se $A \cap B = \emptset$ então $|A \cup B| = |A| + |B|.

• Enunciamento de muitas outras propriedades de uma probabilidade qualquer.

Graças a esse curso eu aprendi um monte de identidades de conjuntos que eu não sabia antes, e que eu nem sei se sei prová-las. Eu aprendi isso porque essas identidades são úteis para calcular probabilidades.

Entendendo o conceito de espaço amostral eu descobri que ao jogar 2 dados, eu sempre devo apostar que vai sair o 10 ou 11.

Aula 14: probabilidade condicional

• Cálculo da probabilidade de 2 pessoas num grupo de $n$ pessoas fazerem aniversário no mesmo dia. Para calcular isso o professor calculou o tamanho do espaço amostral desse experimento que é $365^n$ e depois calculou a probabilidade de nenhuma delas fazer aniversário no mesmo dia.

Uma coisa que eu demorei pra entender é que a cardinalidade de um espaço amostral pode ser uma combinação.

Se o grupo tiver 23 pessoas a probabilidade já é maior que 50%.

• Definição de probabilidade condicional. A fórmula é $P(B/A) = \frac{P(A \cap B)}{P(A)}$.

Essa fórmula nos da um meio de calcular a probabilidade de uma interseção de eventos.

• Prova de propriedades da probabilidade condicional.

• Cálculo de $P(A \cap B \cap C)$ usando a definição de probabilidade condicional. Ficou para casa calcularmos o caso geral $ P(A_1 \cap … \cap A_n)$.

• Um exemplo bobo para treinar probabilidade condicional.

• Cálculo da probabilidade de acertar todas as questões de verdadeiro e falso de um teste com 7 questões sabendo que a maioria era verdadeira. O professor calulou o espaço amostral usando combinação.

• Mais um exemplo (dessa vez difícil) pra treinar probabilidade condicional. Nesse o professor teve que fazer um diagrama.

• Outro exemplo para treinar probabilidade condicional envolvendo dados honestos e viciados.

Não me lembro direito como eram os exemplos.

A probabilidade condicional é uma espécie de probabilidade “a posteriori”, pois é a chance de um evento ocorrer depois de já ter realizado o experimento e ter obtido alguma informação sobre o resultado.

Ainda estou com um pouco de dificuldade pra entender a diferença entre $P(A/B)$ e $P(A \cap B)$.

A teoria de probabilidades responde perguntas sobre experimentos aleatórios. A aleatoriedade pode ser tanto por causa de falta de conhecimento quanto por algo ser intrísicamente aleatório.

Os eventos podem ser basicamente qualquer coisa. Calcular a cardinalidade de um evento é literalmente um problema de análise combinatória.

Acho que só da pra evitar o uso do diagrama de árvores quando a questão pede $P(A \cap B)$ e dá $P(A/B)$.

“Os diagramas são úteis sempre que o experimento aleatório possuir diversos estágios”.

“Fixado $A$, a probabilidade condicional é uma outra possibilidade sobre o espaço amostral”.

Onde estão as aulas 15 a 18:

O professor acabou o conteúdo da P2 bem antes da P2, por isso ele adiantou o conteudo da P3. Optei por colocar essas aulas adiantadas na parte 3 do resumo do curso.

Aula 19: aula de exercícios?

Eu faltei porque estava passando mal.

Aula 20: aula de exercícios

• O professor explicou algumas questões da lista que ele passou.

Uma coisa que gostei foi que ele conseguiu dar nomes direitinho para os eventos de uma questão.

Além disso, ele começou fazendo uma questão de indução difícil estudando a situação quando $n = 1$ e $n = 2$. É assim que um matemático começa a atacar um problema difícil.

Aula 21: P2

• P2

Em minha defesa (até mesmo contra o André do Futuro que esquecerá de como esses últimos dias foram difíceis), eu fiz essa prova no começo de um tratamento psiquiátrico, e a fase de adaptação do remédio que eu estava tomando me deixou extremamente inquieto. Sai da prova em uns 50 minutos.

— publicidade —