(a) By mathematical induction f(2)-f(1)=1, f(3)-f(2)=0, suppose when n<=k, f(n+1)-f(n)=0 or 1 is always right,(of course f(n)<=n when n<=k by this suppose) then when n=k+1 f(k+2)-f(k+1)=f(k+2-f(k+1))-f(k-f(k-1)) by the suppose, f(k+1)-f(k)=0 or 1 or 2, so (k+2-f(k+1))-(k-f(k-1))=2-(f(k+1)-f(k-1))=0 or 1 or 2. since k+2-f(k+1) and k+1-f(k) are <=k, when 2-(f(k+1)-f(k-1)) = 0 or 1, by the suppose , f(k+2)-f(k+1) is 0 or 1 when 2-(f(k+1)-f(k-1)) = 2 ,f(k+1)-f(k-1) =0, by the suppose, f(k+1)=f(k)=f(k-1), then f(k+2)-f(k+1)=f(k+2)-f(k-1)=f(k+2)-f(k+1)+f(k)-f(k-1)=f(k+2-f(k+1))-f(k-2-f(k-3)) how to continue

(b) By mathematical induction suppose when n<=k and if f(n) is odd then f(n+1)=f(n+1) set t is the minimun num over k s.t. f(t) is odd, f(t+1)=f(t+1-f(t))+f(t-f(t-1)) by the suppose f(t) is odd shows f(t-1) is even so f(t)=f(t-1)+1 then t+1-f(t)=t-f(t-1), f(t+1)=2*f(t-f(t-1)) is even hence f(t+1)=f(t)+1 so the proposition is right for n<=t,