finite continued fractions

Question 1

finite continued fraction:

Answer 1

an expression of the form x0 + 1/(x1+(1/….., where x0 is a real number and all other xk are also positive
denoted [x0: x1,…,xn], the xk’s are called elements
can always rewrite as [x0: x1,…,(xn-1),1] as xn!=1 (cause then x(n-1) could just be x(n-1)+1 and drop the xn, and x(n-1)+1>1)

Question 2

{pk}:

Answer 2

p(-2)=0, p(-1)=1, pk=xkp(k-1)+p(k-2) for all k>=0

Question 3

{qk}:

Answer 3

q(-2)=1, q(-1)=0, qk=xkq(k-1)+q(k-2) for all k>=0

Question 4

continued fractions and recurrence relations:

Answer 4

n>=0, w a positive real number such that wqn+q(n-1)!=0, then [x0: x1,…,xn,w]=(wpn+p(n-1))/(wqn+q(n-1))
so [x0: x1,…,xn]=pn/qn

Question 5

pk and qk equations:

Answer 5

pkq(k-1)-p(k-1)qk=(-1)^(k-1)
pkq(k-2)-p(k-2)qk=(-1)^(k)xk

Question 6

finite simple continued fraction:

Answer 6

an expression of the form x0+(1/x1+(1/…. where x0 is an integer and all other xk are also positive

Question 7

qk with fscfs:

Answer 7

qk>q(k-1)>…>q1>=q0>0

Question 8

gcd(pk,qk):

Answer 8

for fscfs and k>=0, gcd(pk,qk)=1 so the fraction pk/qk cannot be simplified

Question 9

the continued fraction algorithm:

Answer 9

let a be a real number
step 1: set a0=a, x0=⌊a0⌋ (integer part of a0), and ε1=a0-x0. if ε1=0, return a=[x0]. otherwise, a=[x0: a1], where a1=1/ε1, proceed to step 2
step k: set x(k-1)=⌊a(k-1)⌋ and εk=a(k-1)-x(k-1). if εk=0, return a=[x0: x1,…,x(k-1)]. otherwise, a=[x0: x1,…,x(k-1),ak] where ak=1/εk, proceed to step k+1

Question 10

continued fraction algorithm terminates:

Answer 10

let a,b be integers with b!=0, it terminates when applied to a/b, assuming the euclidean (different) algorithm terminates at step N, a/n=[m1: m2,…,mN] (m is the multiple not the remainder)
aj in cfa=aj/a(j+1) in ea, x(j-1) in cfa=mj in ea, εj in cfa=rj/a(j+1) in ea
means every rational number can be expressed as a finite Simple continued fraction