Resumos LEIC-A
IST LEIC-AGitHub
Edit page

Indução Matemática

Demonstrações por indução matemática

Relembrando que quando queremos provar uma coleção de enunciados através de Indução Matemática, devem-se provar os seguintes pontos:

  • Que P(0)P(0) é verdadeiro;
  • ∀n∈N (P(n) eˊ verdadeiro  ⟹  P(n+1) eˊ verdadeiro)\forall_{n \in \mathbb N} \ (P(n) \text{ é verdadeiro}\implies P(n+1) \text{ é verdadeiro})

onde P(n)P(n) (antecedente) é a nossa Hipótese de Indução. A sucessão de Fibonacci é um ótimo exemplo de algo donde se podem derivar várias propriedades a partir da indução matemática. É definida da seguinte forma:

fn={ 0se n=0 1se n=1 fn−1+fn−2se n∈Nf_n=\begin{cases}\ 0\quad \text{se } \quad n = 0\\\ 1\quad \text{se } \quad n = 1 \\\ f_{n-1} + f_{n-2}\quad \text{se }\quad n \in \mathbb N\end{cases}

Com termos:

n012345678910fn011235813213455\begin{array}{l|l|l|l|l|l|l|l|l|l|l|l} n&0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline f_n&0 & 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 & 55 \end{array}

Exemplos de aplicações da indução matemática

Primeiro exemplo

Pretende-se provar que:

∑k=0nfk=fn+2−1\sum_{k=0}^{n}f_k = f_{n+2} -1

Base da indução (n = 0)

∑k=00fk=0=1−1=f0+2−1\sum_{k=0}^{0}f_k = 0 = 1-1 = f_{0+2}-1

Hipótese de Indução: ∑k=0nfn=fn+2−1\sum_{k=0}^{n}f_n = f_{n+2} -1

Passo de indução

∑k=0n+1fk=∑k=0nfk+fn+1==fn+2−1+fn+1=fn+3−1\sum_{k=0}^{n+1}f_k =\sum_{k=0}^{n}f_k + f_{n+1}=\\ = f_{n+2}-1+f_{n+1} =f_{n+3}-1

Onde se aplicou a nossa hipótese de indução.

Segundo exemplo

Pretende-se provar que:

∑k=0nfk2=fnfn+1\sum_{k=0}^{n}f_k^2 = f_nf_{n+1}

Base da indução (n = 0)

∑k=00fk2=02=0=0⋅1=f0f0+1\sum_{k=0}^{0}f_k^2 = 0^2=0=0\cdot1=f_0f_{0+1}

Hipótese de Indução: ∑k=0nfk2=fnfn+1\sum_{k=0}^{n}f_k^2 = f_nf_{n+1}

Passo de indução

∑k=0n+1fk2=∑k=0nfk2+fn+12==fnfn+1+fn+12=fn+1(fn+fn+1)=fn+1fn+2\sum_{k=0}^{n+1}f_k^2=\sum_{k=0}^{n}f_k^2+f_{n+1}^2 = \\=f_nf_{n+1}+f_{n+1}^2 = f_{n+1}(f_n+f_{n+1}) = f_{n+1}f_{n+2}

Terceiro exemplo

Pretende-se provar que:

fn−1fn+1=fn2+(−1)nf_{n-1}f_{n+1} = f_n^2 +(-1)^n

Base da indução (n = 1)

f0f2=0⋅1=0=f12+(−1)1=1−1=0f_{0}f_{2}= 0\cdot1 = 0 = f_1^2+(-1)^1=1-1=0

Hipótese de Indução: fn−1fn+1=fn2+(−1)nf_{n-1}f_{n+1} = f_n^2 +(-1)^n

Passo de indução

fnfn+2=fn(fn+1+fn)=fn2+fnfn+1=fn−1fn+1−(−1)n+fnfn+1=fn+1(fn+fn−1)+(−1)n+1=fn+12+(−1)n+1f_{n}f_{n+2} = f_n(f_{n+1}+f_{n}) =\\ f_n^2+f_nf_{n+1} = f_{n-1}f_{n+1}-(-1)^n + f_{n}f_{n+1} =\\ f_{n+1}(f_n+f_{n-1}) + (-1)^{n+1} = f_{n+1}^2 + (-1)^{n+1}

Tipos de indução

Definição de indução simples:

Se P(m),P(m+1),P(m+2),…(m∈N)P(m), P(m+1), P(m+2),\dots ( m \in \mathbb N) é uma sequência infinita de enunciados tal que:

  • P(m)P(m) é verdadeiro;
  • ∀n∈N\forall_{n \in \mathbb N} (P(n)(P(n) é verdadeiro ⟶P(n+1)\longrightarrow P(n+1) é verdadeiro));

Definição de indução completa:

Se P(m),P(m+1),…P(m), P(m+1), \dots são enunciados, então se:

  • P(m),P(m+1),…P(m), P(m+1), \dots são verdadeiros;
  • ∀n∈N,P(m),…,P(m+γ),P(m+γ+1),…,P(m+γ+n)⟶P(m+γ+n+1)\forall_{n \in \mathbb N}, P(m), \dots, P(m+ \gamma), P(m+\gamma+1), \dots, P(m+\gamma+n) \longrightarrow P(m+\gamma+n+1);

então ∀n∈NP(n)\forall_{n \in \mathbb N} P(n) é verdadeiro.

Exemplo de indução completa:

Quer se provar que todo o número natural é a soma de números de Fibonacci não consecutivos.

Base da indução (n = 0)

0 eˊ um nuˊmero de Fibonacci.0~\text{é um número de Fibonacci.}

Hipótese de Indução: Todo o nuˊmero natural eˊ a soma de nuˊmeros de Fibonacci na˜o consecutivos.\text{Todo o número natural é a soma de números de Fibonacci não consecutivos.}

Passo de indução

Tem-se que 0,1,2,3 são números de Fibonacci, pelo que cumprem logo o requisito da prova. Se nn for número de Fibonacci, não há o que provar. Caso contrário, existe jj tal que Fj<m<Fj+1F_j < m < F_{j+1} donde se repara que Fj+1=Fj+Fj−1⇔fi−1>m−fjF_{j+1} = F_j + F_{j-1} \Leftrightarrow f_{i-1} > m - f_{j}, pelo que, se fjf_j vai pertencer ao conjunto DD de números de Fibonacci que vai somar até dar mm, então é impossível fi−1f_{i-1} também pertença ao mesmo conjunto DD (Fj+Fj−1=Fj+1>m).(F_j + F_{j-1} = F_{j+1} > m).

A partir da nossa hipótese de indução, conclui-se que m−fjm-f_j resulta da soma entre números de Fibonacci não consecutivos.

Como resultado,  n\ n pode ser representado como a soma de FjF_j e o conjunto Dm−fjD_{m-f_j}, e está provada a etapa de indução.

Como exemplo, tome-se o número doze como valor para mm:

8<12<138 < 12 < 13

Tem-se que m−fj=12−8=4=3+1m-f_j = 12 - 8 = 4 = 3+1 (sabe-se que tem representação através de números de Fibonacci devido à nossa hipótese). Logo tem-se que:

12=8+4=8+3+112= 8+4 = 8+3+1