T(2)=1+T(0)
=1+1
=2
T(3)=1+T(1)
=2
T(4)=1+T(2)
=3
T(5)=1+T(3)
=3
則數(shù)列為:
1,2,2,3,3,4,4,...
觀察可得:
T(1)-T(0)=0
T(2)-T(1)=1
T(3)-T(2)=0
T(4)-T(3)=1
T(5)-T(4)=0
則:
T(1)-T(0)=[1+(-1)^1]/2
T(2)-T(1)=[1+(-1)^2]/2
T(3)-T(2)=[1+(-1)^3]/2
T(4)-T(3)=[1+(-1)^4]/2
T(5)-T(4)=[1+(-1)^5]/2
...
T(k)-T(k-1)=[1+(-1)^k]/2
將上式相加,得:
T(k)-T(0)
=[1+(-1)^1]/2+[1+(-1)^2]/2+[1+(-1)^3]/2+...+[1+(-1)^k]/2
=[k/2]+(1/2)[(-1)^1+(-1)^2+...+(-1)^k]
=k/2+(1/2)*{(-1)*[1-(-1)^k]/[1-(-1)]}
=k/2-1/4*[1-(-1)^k]
=k/2+(1/4)*(-1)^k-1/4
=(1/4)*(-1)^k+(2k-1)/4
則有:
T(k)=[(1/4)*(-1)^k+(2k-1)/4]+T(0)
=(1/4)*(-1)^k+(2k+3)/4
則:T(k)=(1/4)*(-1)^k+(2k+3)/4