Showing that $2n$ is in the set EVEN from a recursive definition

Question

Define the set EVEN (positive even integers) with two rules:

$1$) $2$ is in even

$2$) if $x,y \in $ EVEN then $x+y \in $ EVEN

I want an efficient method for proving $2n$ is in EVEN. My idea thus far is to first show that $floor(log_2(2n))$ is in even by adding up the highest powers of $2$ already shown to be in EVEN, and then count upwards in increments of $2$ until the number is reached. For instance take $n=7$, then

1)$2$ is in Even

2)$2 + 2 = 4$ is in Even

3)$4+4 = 8$ is in Even

And now add $2$ continually until I get to $14$. This method can take at most $floor(log_2(2n)) + (floor(log_2(2n))-1)) $ steps and I am not sure it is ideal. Any tips for optimization or other ideas (including binary representation) appreciated.

Answer 1

You've got the right idea about using addition to carry it forward, but the method you've chosen may be a bit hard to describe generally. Instead, I recommend adding $2$ each time, rather than sometimes doubling.

Suppose for some positive integer $n$ that we want to prove $2n$ is even. You know that $2=2\cdot1$ is even by definition, so suppose that $n>1.$ If you know that $2k$ is even for some positive integer $k,$ then $2(k+1)=2k+2$ is even. After applying this process (adding $2$) $n-1$ times, you'll have proved that $2n$ is even.

Answer 2

Mathematical Induction is the key.

for $n=1$, we know $2(1) =2$ is even.

If true for $ n$, then $2(n+1)=2n+2$, even plus even is even.

Thus it is true for every $n$

Answer 3

Purely algorithmic approach Initialize the result to res = 0 then compute the powers of two until n == res also & is the bitwise AND

powTwo=2;
while(n != res)
{
   if(n & powTwo) res += powTwo;
   powTwo += powTwo; // Or binary shift powTwo=powTwo<<1;
}

This takes $\log_2(n)$ steps to get from $0$ to $n$ using your recursive definition. It's like looking at the binary representation of $2n$ for $14$ it is $1110$ so to get $1110$ you add $10+100+1000=2+4+8$. Also this could be easily converted to a recursive function.