% This .tex file uses ThaTeX and should be compiled with xetex.
% To obtain and install ThaTeX see:  https://github.com/tsouanas/thatex
\input thatexhandout

\def\PROFESSOR  {Θάνος}
\def\COURSE     {FMC1}
\def\SEMESTER   {2021.2}
\def\HANDOUT    {Problem Set 2}
\def\DEADLINE   {23/01/2022, 23h59}
\def\POINTS     {100 + \bonus{16}}
\def\STUDENT    {}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\fib#1{F_{#1}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mktitle

\rules Regras e esclarecimentos.
\rule: Podes citar como lemma (sem demonstrar) \emph{apenas:}
       (i) teoremas que são \emph{demonstrados} no fmcbook;
       (ii) teoremas que demonstramos na U1 no NNG.
\rule: Nenhuma outra consulta ou colaboração é permitida.
\rule: Todo o Problem Set está no mundo dos naturais; não dos inteiros!
       Isso tem uma conseqüência boa e uma ruim:
       (i) Podes citar como lemma gratuito (sem demonstrar) qualquer
       teorema que já demonstramos na U1 (incluindo os teoremas do NNG).
       (ii) Não podes usar operações e relações de inteiros.
       Por exemplo, não podes usar subtração: se na tua prova aparecer
       uma expressão que envolve subtração, seria um type error e
       tua demonstração sequer compilaria!
\rule: O E1 precisa ser resolvido por indução, e o E2 por recursão.
\rule: O E1 possui duas partes: existência (E1E) e unicidade (E1U).
       (i) Para a existência é obrigatório usar indução (em forma essencial).
       (ii) Para a unicidade não—mas a verdade é que aqui o uso de indução
       será provavelmente escondido nas demonstrações de lemmas
       citados-e-já-demonstrados e não explicitamente exposto no texto
       da tua demonstração.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\Question Problema E1. [64 pts]
Demonstre \emph{por indução} o teorema da divisão de Euclides para naturais:
\statement{para quaisquer naturais $a,b$ com $b \neq 0$,
existem únicos naturais $q,r$ tais que: (i) $a = bq + r$; (ii) $r < b$.}

\Question Problema E2. [\bonus{16} pts]
Define \emph{recursivamente} as funções $\rem$ e $\quot$ nos naturais.
Considere que seu segundo argumento necessariamente terá a forma $Sb$ para algum natural $b$.
Exemplos de ``input--output'':
\mathcols 3
\quot (18,3) &= 6 & \quot (13,5) &= 2 & \quot (7,12) &= 0  \\
\rem  (18,3) &= 0 & \rem  (13,5) &= 3 & \rem  (7,12) &= 7. \\
\endmathcols

\Question Problema F. [36 pts]
Definimos a seqüência dos números Fibonacci pelas
\mathcols 3
\fib {0}   &= 0 &
\fib {S0}  &= 1 &
\fib {SSn} &= \fib {Sn} + \fib n.
\endmathcols
Demonstre que para quaisquer $m,n\in\nats$,
$$
\fib {S(m+n)} = \fib {Sm} \fib {Sn} + \fib m \fib n.
$$

\bye
