Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  Qiaochu Yuan Aug 12 '12 at 17:41
    
@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? –  Timothy Aug 13 '12 at 2: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. –  Gerry Myerson Aug 13 '12 at 3:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.