[题目]已知k∈{0,1,2,3}和正整数n,设fk(n)是序列x1,x2..,xn的个数,其中每个xi∈{-1,0,1},且x1+x2+...+xn≡k (mod 4).证明:(1)f1(n)=f3(n).(2)f0(n)=(3n+2+(-1)n)4. [解答一] 利用递推关系. 根据x_n的值,可以列出f_k(n)的递推关系式,得到递推方程组. 考虑f_1(n)-f_3(n),发现是常数,代入n=1得0,因此f_1(n)=f_3(n). 同理得到f_0(n)-f_2(n)=1.结合f_0+f_1+f_2+f_3=3^n,可以得到(2). [解答二] 组合求解. f_k(n)是g(t)=(1t+1+t)^n中t的幂次模4余k的项的系数和. x_i换成-x_i可以得到f_1和f_3所计数集合的一个对应.因此有(1). 用单位根可以计算一个幂级数中特定余数的幂次的系数和,特别的f_0(n)=(g(1)+g(-1)+g(i)+g(-i))4,其中i^2=-1.