Prova 3 — Técnicas de demonstração, indução e recursão

Como $m$ e $n$ são ímpares, existem $k, j \in \mathbb{Z}$ tais que $m = 2k+1$ e $n = 2j+1$. Assim:

Como $k+j+1 \in \mathbb{Z}$, $m+n$ é da forma $2 \cdot (\text{inteiro})$, logo é par. $\blacksquare$

Suponha $n$ ímpar, isto é, $n = 2k+1$ para algum $k \in \mathbb{Z}$. Então:

Como $3k+2 \in \mathbb{Z}$, $3n+2$ é da forma $2 \cdot (\text{inteiro})+1$, logo é ímpar. Pela contrapositiva, se $3n+2$ é par, então $n$ é par. $\blacksquare$

Suponha, por contradição, que $\sqrt{6}$ é racional. Então existem $p, q \in \mathbb{Z}$, $q \ne 0$, com $\gcd(p,q)=1$ (fração irredutível), tais que $\sqrt{6} = p/q$. Elevando ao quadrado:

Logo $p^{2}$ é par, o que implica $p$ par (se $p$ fosse ímpar, $p^{2}$ seria ímpar). Escreva $p = 2k$, $k \in \mathbb{Z}$. Substituindo:

Assim $3q^{2}$ é par, e como $3$ é ímpar, $q^{2}$ é par, o que implica $q$ par. Mas se $p$ e $q$ são ambos pares, isso contradiz $\gcd(p,q)=1$. Essa contradição mostra que a suposição inicial é falsa, logo $\sqrt{6}$ é irracional. $\blacksquare$

Base ($n=1$): $2^{2(1)} = 4$, que é divisível por $4$. ✓

Passo indutivo: suponha que $2^{2k}$ é divisível por $4$ para algum $k \ge 1$, isto é, $2^{2k} = 4m$ para algum $m \in \mathbb{Z}$. Mostremos para $k+1$:

Como $4m \in \mathbb{Z}$, $2^{2(k+1)}$ é divisível por $4$. Por indução, vale para todo $n \ge 1$. $\blacksquare$

Base ($n=1$): $1 = \dfrac{1(1+1)}{2} = 1$. ✓

Passo indutivo: suponha $1+2+\ldots+k = \dfrac{k(k+1)}{2}$ para algum $k \ge 1$. Mostremos para $k+1$:

Que é exatamente a fórmula para $n=k+1$. Por indução, vale para todo $n \ge 1$. $\blacksquare$

Como $a$ é ímpar, $a = 2k+1$ para algum $k \in \mathbb{Z}$. Então:

Como $2k^{2}+5k+5 \in \mathbb{Z}$, $a^{2}+3a+7$ é da forma $2 \cdot (\text{inteiro})+1$, logo é ímpar. $\blacksquare$

Base ($n=1$): $1 = 1^{2}$. ✓

Passo indutivo: suponha $1+3+\ldots+(2k-1) = k^{2}$ para algum $k \ge 1$. Mostremos para $k+1$:

Que é exatamente a fórmula para $n=k+1$. Por indução, a equação vale para todo inteiro positivo $n$. $\blacksquare$

Pela definição recursiva da sequência de Fibonacci, $F(k) = F(k-1)+F(k-2)$ para todo $k>2$. Aplicando essa recorrência duas vezes a partir de $F(n+4)$:

Aplicando a recorrência novamente em $F(n+3)$:

Substituindo:

Da recorrência em $F(n+2) = F(n+1)+F(n)$, isolamos $F(n+1) = F(n+2)-F(n)$. Substituindo:

Como a igualdade decorre diretamente da fórmula de recorrência de Fibonacci, aplicada a cada $n>0$, ela vale para todo $n \in \mathbb{N}$, $n>0$. $\blacksquare$