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.

  • 0
    By induction it suffices to show that the first term is unique. This boils down to showing that the first term must be the floor.2012-08-12
  • 0
    @QiaochuYuan Thanks for your hint but can you be a bit more elaborate. I have p_0 = q_0 + r/s where s/r = [q_1,...,q_m], and how do I show that m=0 and p_0 = q_0? It seems that p_0-q_0=r/s is a natural number so either s=1 or r=0 (my desired conclusion). What have I been missing?2012-08-13
  • 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