This question concerns Peano arithmetic. We define addition $+$ and multiplication

$$by the following rules:

$+($a$,0)=$ a

$+($a$,$ S$($b$))=$ S$(+($a$,$ b$))$

$($a$,0)=0$

$($a$,$ S$($b$))=+($a$,($a$,$ b$))$

Using only the axioms of Peano arithmetic, prove the following results. You may use results proven in earlier parts to prove later parts. Do not use identities or equalities that you have not first proven, no matter how obvious they might seem! $($Hint: You will find the Peano arithmetic definition of induction very useful.$)$

a$.+(0,$ b$)=$ b

b$.+($S$($a$),$ b$)=$ S$(+($a$,$ b$))$

c$.+($a$,$ b$)=+($b$,$ a$)($Commutativity of $+)$

d$.+($a$,+($b$,$ c$))=+(+($a$,$ b$),$ c$)($Associativity of $)$

e$.(0,$ b$)=0$

f$.($S$($a$),$ b$)=+($b$,($a$,$ b$))$

g$.($a$,$ b$)=($b$,$ a$)($Commutativity of $)$

Results a$.$ and b$.$ are proven below to give you a starting point.

Proof of a$.$ We will prove this by induction over b$.$ Let P $($b$)$ be $+(0,$ b$)=$ b$.$

$+(0,0)=0($Definition of $+)$

This proves P $(0).$ Now, assume that P $($b$)$ holds, and derive that P $($S$($b$))$ holds.

$+(0,$ S$($b$))=$ S$(+(0,$ b$))($Definition of $+)$

$=$ S$($b$)($P $($b$))$

Thus, P $(0)$ holds and P $($b$)$ P $($S$($b$))$ for all Peano numbers b$,$ so by induction, the result holds.

Proof of b$.$ We will prove this by induction over b$.$ Let P $($b$)$ be $$a$.+($S$($a$),$ b$)=$ S$(+($a$,$ b$)).$

$+($S$($a$),0)=$ S$($a$)($Definition of $+)$

$=$ S$(+($a$,0))($Definition of $+)$

This proves P $(0).$ Now, assume that P $($b$)$ holds, and derive that P $($S$($b$))$ holds.

$+($S$($a$),$ S$($b$))=$ S$(+($S$($a$),$ b$))($Definition of $+)$

$=$ S$($S$(+($a$,$ b$)))($P $($b$))$

$=$ S$(+($a$,$ S$($b$)))($Definition of $+)$

Thus, P $(0)$ holds and P $($b$)$ P $($S$($b$))$ for all Peano numbers b$,$ so by induction, the result holds.

Problem $2$: Suppose you have $5$ glasses on the table, all face$-$down. You are allowed to pick up two glasses at once, one in each hand, and flip over both of them. You may do this as many times as you like, and your goal is to have all the glasses facing up$.$

a$.$ Is this possible? If so$,$ what is the procedure? If not, give a proof for why you cannot.

b$.$ What about if there were $6$ glasses on the table initially, all facing down?

c$.$ Give an answer for any n in N$,$ where you start with n glasses face$-$down, and can only ever flip exactly two.

Problem $3$: This problem concerns the Extended Euclidean Algorithm and gcds$.$

a$.$ Calculate gcd$(60192,47310)$ using the Extended Euclidean Algorithm, and express it as a linear combination of $60192$ and $47310.$

b$.$ Consider the Fibonacci numbers. What is gcd$($Fn$+1,$ Fn$)$ as a function of n in N$?($Hint: It might help to calculate gcd$($Fn$+1,$ Fn$)$ for a few small values of n first.$)$

c$.$ Consider the Extended Euclidean Algorithm run on two natural numbers. Prove that for any k $0$ such that rk$+2$ is defined, rk$+2<$ rk$/2.($Hint: You might want to consider two cases, concerning rk$+1$ and rk$/2.)$