3的乘冪、遞迴數列、高斯函數(10點)

Question

考慮兩個遞迴數列：fm=[(fm-1)/3]gm=fm-3*fm+1其中f0=k，k為非負整數若存在非負整數p使得fp+1=0，(1)證明對於任意非負整數m而言，gm的值只可能是0或1或2..................p(2)證明k=Σgn*3n................n=0很瑣碎的題目...........

Answer 1

對於任意非負整數k, 存在 r 為非負整數
k= Ar 3^(r-1) + .... + A0 3^0
其中 Ai = 0 或 1 或 2 for all 1≦i≦r, 且Ar=\=0.(3進位表示法)
Claim:
f s = Ar 3^(r-s) +...+ As 3^0 for all 0≦s≦r -----(*)
r=0 is trivial.
假設 r > 0.
當 s=0,
f0= Ar 3^(r) +...+ A1 3^0 成立
假設 s = j ≦ r-1成立
當 s = j+1≦r
f(j+1) =[fj/3]=[ ( Ar 3^(r-j-1) +...+ A(j+1) 3^0 ) + (Aj / 3) ]= Ar 3^(r-(j+1)) +...+ A(j+1) 3^0 成立
故由歸納法成立!
由 (*) 很容易證明, g s = f s - 3[ f s /3] = As for all 0≦s≦r
故 gs 的值只可能是0或1或2.
由Cliam, f j = 0 for all j≧r+1. 所以 g j = f j - 3[f j / 3]=0 for all j≧r+1.
故若存在非負整數p使得 fp+1=0 必為 p≧r.(因為Ar=\=0,所以f j > 0 for 0≦j≦r)
Σ(n=0 to p)gn*3^n = Σ(n=0 to r)gn*3^n = Σ(n=0 to r)gn*3^n=Σ(n=0 to r)An*3^n=k.