## Proving correctness, algorithm [closed]

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.

-
This not for MathOverflow, although it might be appropriate for math.atackexchange. However, I recommend writing out a few cases for n and k, say up to 10, and replacing the numbers involved by their residues mod 2. That should reveal some of the issues involved in a proof. Gerhard "Ask Me About System Design" Paseman, 2012.03.03 – Gerhard Paseman Mar 3 2012 at 20:34
The question is probably more suitable for [MSE](math.stackexchange.com). – Kaveh Mar 3 2012 at 20:51
A useful observation: $\binom{n}{k} \equiv 0 \mod 2 \iff n \leq k$ bitwise. – Johannes Hahn Mar 3 2012 at 21:25
And yet upon setting k to n, I get something different. Perhaps Johannes means something else. Gerhard "Ask Me About System Design" Paseman, 2012.03.03 – Gerhard Paseman Mar 3 2012 at 23:10