2
$\begingroup$

I have problems proving the uniqueness of simple continued fraction representation of rational numbers as claimed in http://en.wikipedia.org/wiki/Continued_fraction#Finite_continued_fractions.

Let $r$ be a rational number with representation $[p_0,p_1,...,p_n]$ where $p_n\neq 1$. I want to prove that this representation is unique, i.e. if $[q_0,q_1,...,q_m]$ is another representation then $m=n$ and the $p$'s are equal to the $q$'s.

I know that this must be done by induction on $n$ but somehow I dont know how to proceed, even in the base case (that is $p_0\neq 1$ and conclude $m=0$). Any hints is much appreciated.

  • 1
    Qiaochu probably intends for you to show that if $r=[p_0,p_1,\dots,p_n]=[q_0,q_1,\dots,q_m]$ then $p_0=q_0=[r]$, and then apply this result to $(r-p_0)^{-1}$ whilst invoking induction.2012-08-13

1 Answers 1

0

Formal proof by induction goes like this: if $x = [p_0; \mathcal P]$ where $\mathcal P$ is $[p_1; p_2, ..., p_n]$ (could be empty) then from $p_n \neq 1$ (if $\mathcal P$ is non-empty) follows that $||\mathcal P|| > 1$ therefore $p_0 \leq x < p_0+1$; indeed $x = p_0 + 1/||\mathcal P||$$||\mathcal P||$ here denotes numeric value of representation $\mathcal P$. Therefore $p_0 = \lfloor x \rfloor$ and thus is uniquely determined by $x$. Then you get $x-p_0 = [\mathcal P]$ and by induction $\mathcal P$ is uniquely determined by $x-p_0$ and therefore entire representation $x = [p_0; p_1,...,p_n]$ is uniquely determined.