Lista 3: Técnicas de demonstração, indução e recursão

Como $x$ e $y$ são pares,

Como $a, b \in \mathbb{Z} \Rightarrow a+b \in \mathbb{Z}$.

Como $n$ é ímpar, $n = 2a+1$, com $a \in \mathbb{Z}$.

Como $a \in \mathbb{Z} \Rightarrow 2a^{2}+a \in \mathbb{Z}$.

Como $a \in \mathbb{Z} \Rightarrow 3a \in \mathbb{Z}$.

Pela contrapositiva, supomos que $n$ é par:

Logo, $3n+2$ é par, ou seja $\lnot q \Rightarrow \lnot p$.

Pela contrapositiva, supomos $a > \sqrt{n}$ e $b > \sqrt{n}$.

Logo, $n = a \cdot b > n$, contradizendo a hipótese, ou seja $\lnot q \Rightarrow \lnot p$.

Suponha, por contradição, que $x+x=x$ e $x \ne 0$.

Como $x \ne 0$, podemos dividir os dois lados por $x$:

Absurdo. Logo a suposição $x \ne 0$ é falsa.

Como $a \in \mathbb{Z} \Rightarrow 2a^{2} \in \mathbb{Z}$.

Suponha, por contradição, que $\sqrt{2}$ é racional:

Logo $a^{2}$ é par $\Rightarrow a$ é par (Questão 8). Então $a = 2k$, com $k \in \mathbb{Z}$:

Logo $b^{2}$ é par $\Rightarrow b$ é par.

Como $a$ e $b$ são pares, ambos têm o fator $2$ em comum, o que contradiz a hipótese de que são primos entre si $(\rightarrow\leftarrow)$.

Como $k, q \in \mathbb{Z} \Rightarrow k+q+1 \in \mathbb{Z}$.

Como $k, q \in \mathbb{Z} \Rightarrow 2kq+k+q \in \mathbb{Z}$.

Suponha, por contradição, que $x \cdot y$ é ímpar mas $x$ e $y$ são pares.

Logo $x \cdot y$ é par, contradizendo a hipótese $(\rightarrow\leftarrow)$.

Pela contrapositiva, suponha $a > 1$.

Ou seja, $\lnot q \Rightarrow \lnot p$.

Sejam $a = i$, $b = i+1$ e $c = i+2$, com $i \in \mathbb{Z}$.

Como $i \in \mathbb{Z} \Rightarrow i+1 \in \mathbb{Z}$.

Como $k \in \mathbb{Z} \Rightarrow 2k^{2}+5k+4 \in \mathbb{Z}$.

Caso $n$ par: $n = 2k$, com $k \in \mathbb{Z}$.

Caso $n$ ímpar: $n = 2q+1$, com $q \in \mathbb{Z}$.

Em ambos os casos, $n^{2}+3n+4 = 2(\text{inteiro})$.

Caso $n$ par: $n = 2k$, com $k \in \mathbb{Z}$.

Caso $n$ ímpar: $n = 2q+1$, com $q \in \mathbb{Z}$.

Em ambos os casos, $5n^{2}+3n+1 = 2(\text{inteiro})+1$.

Pela contrapositiva, suponha $x$ par: $x = 2i$, com $i \in \mathbb{Z}$.

Logo $7x+9$ é ímpar, ou seja $\lnot q \Rightarrow \lnot p$.

Pela contrapositiva, suponha $x$ par: $x = 2k$, com $k \in \mathbb{Z}$.

Como $5$ é ímpar, essa expressão é ímpar, ou seja $\lnot q \Rightarrow \lnot p$.

Pela contrapositiva, suponha $y > x$.

Ou seja, $\lnot q \Rightarrow \lnot p$.

Suponha, por contradição, que existe $x \in \mathbb{R}$ tal que

Absurdo.

I) Se $n=1 \Rightarrow 2(1)-1 = 1^{2} \Rightarrow 1=1$. A equação é verdadeira para $n=1$ (passo básico).

II) Vamos supor, por indução, que a equação seja verdadeira para algum inteiro $k$. Assim,

III) Vamos demonstrar que $P(k) \Rightarrow P(k+1)$. Assim,

I) Se $n=1 \Rightarrow 2^{2(1)}-1 = 3m$, com $m \in \mathbb{Z} \Rightarrow 4-1=3 \Rightarrow 3=3$. A equação é verdadeira para $n=1$ (passo básico).

II) Vamos supor, por indução, que a equação é válida para algum inteiro positivo $k$. Assim,

III) Vamos demonstrar que $P(k) \Rightarrow P(k+1)$. Assim,

I) Se $n=1 \Rightarrow 1 = \dfrac{1(1+1)}{2} \Rightarrow 1=1$. A equação é verdadeira para $n=1$ (passo básico).

II) Vamos supor, por indução, que a equação seja verdadeira para algum inteiro $k$. Assim,

III) Vamos demonstrar que $P(k) \Rightarrow P(k+1)$. Assim,

Suponha, por contradição, que existe solução inteira. Fatorando:

Como $x, y \in \mathbb{Z}$, os fatores $(x+y)$ e $(x-y)$ têm sempre a mesma paridade entre si (ambos pares ou ambos ímpares), pois sua diferença $(x+y)-(x-y) = 2y$ é sempre par. Os divisores de $10$ são $\pm1, \pm2, \pm5, \pm10$, e qualquer par deles com produto $10$ mistura um fator par com um ímpar ($1 \times 10$, $2 \times 5$, e seus sinais), nunca dois da mesma paridade:

Como $(x+y)$ e $(x-y)$ precisam ter a mesma paridade, mas nenhuma fatoração de $10$ oferece isso, não existem $x+y$ e $x-y$ inteiros cujo produto seja $10$, absurdo.

I) Se $n=1 \Rightarrow 1^{3} = 1^{2} \Rightarrow 1=1$. A equação é verdadeira para $n=1$ (passo básico).

II) Vamos supor, por indução, que a equação seja verdadeira para algum inteiro $k \ge 1$. Assim,

III) Vamos demonstrar que $P(k) \Rightarrow P(k+1)$. Usando o resultado da Questão 24, $1+2+\ldots+k = \dfrac{k(k+1)}{2}$:

I) Se $n=1 \Rightarrow 2^{1} > 1 \Rightarrow 2 > 1$. Verdadeiro (passo básico).

II) Vamos supor, por indução, que a desigualdade seja verdadeira para algum inteiro $k$. Assim,

III) Vamos demonstrar que $P(k) \Rightarrow P(k+1)$. Assim,

Como $k \ge 1 \Rightarrow 2k \ge k+1$ (pois $2k-(k+1) = k-1 \ge 0$), então

I) Se $n=1 \Rightarrow 1\cdot2 = \dfrac{1(1+1)(1+2)}{3} \Rightarrow 2 = \dfrac{6}{3} \Rightarrow 2=2$. A equação é verdadeira para $n=1$ (passo básico).

II) Vamos supor, por indução, que a equação valha para algum inteiro positivo $k$. Assim,

III) Vamos demonstrar que $P(k) \Rightarrow P(k+1)$. Assim,

I) Se $n=2 \Rightarrow 2^{2} > 2+1 \Rightarrow 4 > 3$. Verdadeiro (passo básico).

II) Vamos supor, por indução, que a desigualdade seja verdadeira para algum inteiro $k \ge 2$. Assim,

III) Vamos demonstrar que $P(k) \Rightarrow P(k+1)$. Assim,

Como $k \ge 2 \Rightarrow 3k+2 \ge k+2$ (pois $3k+2-(k+2) = 2k \ge 0$), então

I) Se $n=4 \Rightarrow 4^{2} > 3(4) \Rightarrow 16 > 12$. Verdadeiro (passo básico).

II) Vamos supor, por indução, que a desigualdade seja verdadeira para algum inteiro $k \ge 4$. Assim,

III) Vamos demonstrar que $P(k) \Rightarrow P(k+1)$. Assim,

Como $k \ge 4 \Rightarrow 5k+1 > 3k+3 = 3(k+1)$ (pois $5k+1-(3k+3) = 2k-2 > 0$), então

I) Se $n=1 \Rightarrow F(5) = 3F(3)-F(1) \Rightarrow 5 = 3(2)-1 \Rightarrow 5=5$. Verdadeiro (passo básico).

II) Vamos supor, por indução, que a equação seja verdadeira para algum inteiro positivo $k$. Assim,

III) Vamos demonstrar que $P(k) \Rightarrow P(k+1)$, ou seja, que $F(k+5) = 3F(k+3)-F(k+1)$. Assim,

Como $F(k+2) = F(k)+F(k+1) \Rightarrow -F(k) = F(k+1)-F(k+2)$:

Como $F(k+3) = F(k+2)+F(k+1) \Rightarrow F(k+2) = F(k+3)-F(k+1)$: