## 117b – Undecidability and Incompleteness – Lecture 2

The core of the proof of the undecidability of the tenth problem is the proof that exponentiation is Diophantine. We reduced this to proving that certain sequences given by second-order recurrence equations are Diophantine. These are the Matiyasevich sequences: For $b\ge 4$,

$\alpha_b(0)=0$,
$\alpha_b(1)=1$, and
$\alpha_b(n+2)=b\alpha_b(n+1)-\alpha_b(n)$ for all $n$.

We begin the proof that they are Diophantine by analyzing some of the algebraic identities their terms satisfy.