We have a function $F$ defined on the natural numbers and defined below:
function F(n,k)
begin
if k=0 then return 1
else if (n mod 2 = 0) and (k mod 2 = 1) then return 0
else return F(n div 2, k div 2);
end;
where $n \ \text{div}\ 2 = \left\lfloor\frac{n}{2}\right\rfloor$
the task is to prove that $F(n,k)= \begin{cases} 1 \Leftrightarrow {n \choose k} \ \text{mod} \ 2 = 1; \ 0 \text{ otherwise } \end{cases} $
It does not look very complicated (am I wrong?), but I don't know how does this kind of proof should be structured.
I think, maybe inductive approach may be good? I want to prove that if for some $n,k$ I have good result for $F(n,k)$ then I have good results for: $F(2n,2k); \ F(2n+1,2k); \ F(2n,2k+1); \ F(2n+1,2k+1)$ but I don't know if it is correct and how to prove the base:
if k=0 then return 1
else if (n mod 2 = 0) and (k mod 2 = 1) then return 0
and if it's sufficient, and why. I would be very grateful for help.
