Note fn:= an−1 = an−m(am−1)+an−m−1, i.e. fn=fn−m+k fm, k∈Z. Now apply
Theorem Let fn be an integer sequence with f0=0 and fn≡fn−m (mod fm) for n>m. Then (fn,fm) = f(n,m) where (i,j) denotes gcd(i,j).
Proof By induction on n+m . The theorem is trivially true if n=m or n=0 or m=0.
So we may assumen>m>0 . Note (fn,fm)=(fn−m,fm) follows from the hypothesis.
Since (n−m)+m < n+m, induction yields (fn−m,fm)=f(n−m,m)=f(n,m).
See also this post for a conceptual proof exploiting the innate structure - an order ideal.
Theorem
Proof
So we may assume
Since
See also this post for a conceptual proof exploiting the innate structure - an order ideal.
0 comments:
Post a Comment
Don't Forget to comment