Can every number be written as $2^{a_1}+\cdots+2^{a_n} + 1$?

Question

I am reading an algorithm that calculates $x^y$. Basically it is about an implementation of a function $power(x, y)$ where $x$ is the base and $y$ is the exponent i.e. the power.
The algorithm uses successive powers of two and is as follows:

result = 1     
while y not equal to 0   
  if y is not even  
     result = result * x  
  x = x * x  
  shift y 1 bit to the right  
end while  
return result  

The check for if y is not even is by checking the least significant bit.
In any case this algorithm seems to work in all the test cases and from what I see it comes down to multiplying powers of $2$ with $x$.
E.g. for $x^7$ since $7 = 111$ we essentially end up with:
$result = x\cdot x^2\cdot x^4$

Now I can see the connection with the binary representation since if we successively square the exponent increases by powers of $2$ and hence that shift helps with the successive squaring.
So what I want to ask is the following: I think the underlying assumption is that any number can be broken to successive powers of $2$ plus one i.e. $2^n + 1$ since $x^7 = x^{1 + 2 + 4}$.
So is there a formal principle for this i.e. same as we have prime decomposition?

Answer 1

Clearly, the number should be a natural number. So, if it is a natural number, assume WLOG that it is even. (If it is odd, then it is 1 + some even number). Now, your question reduces to, can every even number be reduced to the sum of powers of 2? Note that an even number is 2n, for some $n \in \mathbb{Z}^+$. Thus, an even number is 2 + 2 + ... 2, summed n times. Now, your claim holds if, $\forall n \in \mathbb{Z}^+, 2n = \sum_{\alpha \in I} 2^\alpha$, for $I \subset \mathbb{N}$.

We will prove this by induction. For n = 1, $2 = 2$, so it is trivially true. Assume true for $n = k$ that $2k = \sum_{\alpha \in I} 2^\alpha$, where $I$ has some arbitrary maximum number $m$, say (it must have one, since $N$ is well-ordered). Then, for $n = k+1$, we have $2(k+1) = 2k + 2 = (\sum_{\alpha \in I} 2^\alpha) + 2$. Now, if $1 \notin I$, then our claim holds. However, if $1 \in I$, then our sum becomes $4 + \sum_{\alpha \in I, \alpha \neq 1} 2^\alpha$. Again, if $2 \notin I$, our claim holds. This argument can be repeated for $ 1 \leq j \leq m $ to show that, if for some such $j$, $j \notin I$, then our claim holds.

However, assume that our set $I$ includes all integers from $1$ through $m$. Then, our number is of the form $2 + 4 + 8 + ... + 2^m + 2$. But note that this is just $2^{m+1}$, since $2 + 2 + 4 + 8 + ... + 2^m = 2 + 2(2^m - 1) = 2^{m+1}$, by applying the geometric series formula. QED.

Answer 2

The way to prove that an algorithm works is by augmenting it with comments about the state, and to show that the comment attached to a line is true after a line executes if the comment attached to any possible direct predecessor line (including "jumps" from elsewhere) is true.

Here we can do (where $z$ is the unchanged result of the power to be computed):

result = 1   //  z = x^y  and result = 1
while y is not equal to 0 //  z = result * x^y and for some m, y=2m or y=2m+1
  if y is odd  // y=2m and z = result * x^(2m), or y=2m+1 and z=result * x^(2m+1)
    result = result * x  // z = result * x^(2m) and y = 2m+1
  end if // z = result * x^(2m) and (y = 2m or y = 2m+1)
  x = x * x // z = result * x^m and (y = 2m or y = 2m+1)
  shift y right by 1 // z = result * x^m and y = m, i.e., z = result * x^y
end while //  z = result * x^y
return result //  y = 0 and result = z

I leave it to you that the logical connection between the comments is actually satisfied. It follows that when the code returns, it returns the correct result.