most recent 30 from http://mathoverflow.net 2013-05-19T11:44:38Z http://mathoverflow.net/feeds/question/90141 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/90141/proving-correctness-algorithm xan 2012-03-03T19:56:29Z 2012-03-03T19:56:29Z

<p>We have a function $F$ defined on the natural numbers and defined below:</p> <pre><code>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; </code></pre> <p>where $n \ \text{div}\ 2 = \left\lfloor\frac{n}{2}\right\rfloor$</p> <p>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} $</p> <p>It does not look very complicated (am I wrong?), but I don't know how does this kind of proof should be structured.</p> <p>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:</p> <pre><code>if k=0 then return 1 else if (n mod 2 = 0) and (k mod 2 = 1) then return 0 </code></pre> <p>and if it's sufficient, and why. I would be very grateful for help.</p>