Matemática Discreta - Aula 06

Princípio da Indução Finita (PIF)

Utilizado para provar propriedades de uma sequência ou série.

[!note] SEQUÊNCIA Elementos seguinda um padrão de construções.

[!note] SÉRIE Soma de uma sequência

Três condições

Exemplo 1

Prove para $n\ge1$ que $1+3+5+\dots+(2n-1)=n²$

####### Obs da Sequência

$$ \begin{align} 2n-1\ n = 1 \implies (2×1)~1 = 2 - 1 = 1\ n = 2 \implies (2×2)-1 =4 - 1 = 3\ \dots \implies 2n-1 \text{ é a regra da sequência} \end{align} $$

####### Obs da Série

$$ \begin{align} n = 3 \quad \implies n^2 = 3^2 = 9 \ 1+3+5 = 9 \ \ n = 5 \implies 1+3+5+7+9 = 25 = 5^2 \ \text{A soma de n elementos da sequência é igual a }n^2 \end{align} $$

####### Solução 1 (PIF 1.)

Se $n=1$ temos o primeiro elemento como 1 e o “lado direito”, isto é, a finalização, sendo resultado $1$ também. Portanto $\implies$ igualdade válida para o 1º elemento

[!info] NÃO É O N MAS O ELEMENTO No caso, declaramos que $n=1$ mas o $n_0$ já era 1 na sequência. Estamos substituindo o $n$ nas observações da Série e Sequência. Assim, ficando $$\begin{align}2n-1 = n^2 \ 2×1-1 = 1^2 \ 1=1 \ 1\text{ é igual à primeira posição na sequência? (sim), logo → a Prova para base está válida}\end{align} $$

####### Solução 2 (PIF2)

Suponha verdade para $n=k$. OU seja, se $n=k$, temos $1+3+5+\dots+(2×k-1)=k^2$ onde k é um número qualquer. E assumo isso como verdade. Se isso é verdade…

####### Solução 3 (PIF3)

Vamos provar que $n=k+1$. Assim, acrescentamos um elemento no lado esquerdo da sequência/série.

$$ \begin{align} \underbrace{1+3+5+\dots+(2k-1)}_{k^2}+[2(k+1)-1] = (k+1)^2 \ \ \text{como afirmamos na solução dois, temos:} \ k^2 + [2(k+1)-1] = (k+1)^2 \ k^2 + 2k + 2 -1 = (k+1)^2 \implies k^2+2k+1 \text{ lado esquerdo} \ \ (k+1)^2 \implies k^2 + 2k + 1 \text{ lado direito| binômio perfeito} \ \ \ \text{portanto } \implies k^2+2k+1 = k^2+2k+1 \quad \text{Provado} \end{align} $$

Exercícios

a) $1+2+3+\dots+n = \frac{n×(n+1)}{2}$

• Prova para a base
  • $$1 = \frac{1×(1+1)}{2} \implies \frac{2}{2} = 1 $$
  • Logo, a primeira posição está provada.
• Supor a verdade
  • $$ n=k \implies 1+2+3+\dots+k=\frac{k×(k+1)}{2} $$
• Tese indutiva
  • $$\begin{align} n=k+1 \ \ \implies \qquad \underbrace{\frac{(k+1)\cdot(k+1)}{2} + (k+1)}{\text{lado esquerdo}} = \underbrace{\frac{(k+1)\cdot(k+2)}{2}}{\text{lado direito}} \ \ \ \text{lado esquerdo} \implies \frac{(k+1)\cdot(k+1)+(k+1)}{2} \ \implies \frac{k\cdot(2k+2)}{2} \implies \frac{2k^2+2k}{2} \ \ \ \text{lado direito} \implies \frac{}{} \end{align}$$

Notação Sigma (Somatório)

$$\sum_{\underbrace{i=x}_\text{índice inicial}}^{\overbrace{k}^\text{índice final}} \text{regra}$$

Devemos somar a regra do índice inicial até o final com o índice acrescido de uma unidade a cada passo.

[!info] A Regra pode, ou não, depender do índice.

####### Exemplo

$$ \sum_{i=x}^k \text{regra} = \underbrace{regra}{i=x} + \underbrace{regra}{i=x} + \dots + \underbrace{regra}_{i=k} $$

Expanda o somatório: $$ \begin{align} \sum_{i=3}^5i^2 = \underbrace{3^2}{i=3} + \underbrace{4^2}{i=4} + \underbrace{5^2}_{i=5} \end{align} $$

Expanda o somatório: $$ \begin{align} \sum_{z=2}^6 z+2^z = \underbrace{(2+2^2)}{z=2} + \underbrace{(3+2^3)}{z=3} + \underbrace{(4+2^4)}{z=4} + \underbrace{(5+2^5)}{z=5} + \underbrace{(6+2^6)}{z=6} \end{align} $$ Por fim, o seguinte somatório $$ \begin{align} \sum{k=0}^3 w^4 = \underbrace{(w^4)}{k=0} + \underbrace{(w^4)}{k=1} + \underbrace{(w^4)}{k=2} + \underbrace{(w^4)}{k=3} \end{align} $$ Obs: Acima temos uma regra que não depende do índice. Assim, a regra se mantém, enquanto somamos um ao índice até ele chegar ao índice final

Exercício para fixação

Monte a soma apresentada na notação Sigma.

a) $8^5 + 8^6 + 8^7 + \dots + 8^{21}$

resposta: $$ \sum_{i=5}^{21}8^i $$

b) $5^9+4^{10}+3^{11}+2^{12}$ resposta: $$ \sum_{i=6}^9(11-i)^{(i+3)} $$

Expanda a somatória a) $$\sum_{k=0}^6\frac{1}{k!}$$ resposta: $$ \sum_{k=0}^6\frac{1}{k!} = \frac{1}{1} + \frac{1}{1} + \frac{1}{2} + \frac{1}{6} + \frac{1}{24} + \frac{1}{120} + \frac{1}{720} = \ 2.71805 $$

b) $$\sum_{k=0}^4\frac{2}{(4k+1).(4k+3)}$$ resposta $$ \begin{align} \frac{2}{(4 \ . 0+1) \ . \ (4 \ . 0+3)} \+ \frac{2}{(4 \ . 1+1) \ . \ (4 \ . 1+3)} \+ \frac{2}{(4 \ . 2+1) \ . \ (4 \ . 2+3)} \+ \frac{2}{(4 \ . 3+1) \ . \ (4 \ . 3+3)} \+ \frac{2}{(4 \ . 4+1) \ . \ (4 \ . 4+3)} \ \ \frac{2}{(1) \ . \ (3)} + \frac{2}{(5) \ . \ (7)} + \frac{2}{(9) \ . \ (11)} + \frac{2}{(13) \ . \ (15)} + \frac{2}{(17) \ . \ (19)} \ \ \frac{2}{3} + \frac{2}{35} + \frac{2}{99} + \frac{2}{195} + \frac{2}{323} = 0.76045 \end{align} $$

Propriedades da Notação Sigma

• Podemos falar que a somatória da “soma de duas regras” é a mesma coisa de fazer a soma do primeiro item + a soma do segundo item: $$\sum_i(a_i+b_i) \equiv \sum_ia_i + \sum_ib_i$$
• Sempre que temos uma constante, podemos retirá-la [a constante] para fora da soma: $$\begin{align} \sum_ik \ . \ a_i \equiv k \ . \sum_ia_i \ \ \sum_{i=1}^{4} 10 = 10 \ . \sum_{i=1}^41 \ \ = 10 \ . \underbrace{(1+1+1+1)}_4 = 40 \end{align}$$
• Temos, também, como dividir uma somatória a partir de dois pontos, nós particionamos (“quebramos”) a notação sigma em duas partes que, somando as duas, resultará no mesmo: $$ \sum_{i=x}^na_i = \sum_{i=x}^ka_i + \sum_{i=k+1}^na_i$$ $$ \sum_{i=1}^{10}1 = \sum_{i=1}^51 + \sum_{i=6}^{10}1 $$