# How can I prove the correctness of this exponentiation algorithm using induction?

I have the following algorithm. How could I prove it using induction that for every $$n\ge 0$$, Exp(n)$${}= 2 ^ n$$?

Exp(n)
If n = 0
Return 1

If n is even
temp = Exp(n/2)
Return temp × temp
Else
temp = Exp((n−1)/2)
Return temp × temp × 2

• What does it mean to "prove an algorithm"? You can only prove some property of the algorithm... what property are you looking to prove here? What did you attempt? Oct 28 '20 at 12:20
• i forgot that part. I just eddit now Oct 28 '20 at 12:29

$$Exp(0) = 1 = 2^0$$ is trivially correct (hard coded) by the algorithm.

Assume the algorithm holds for values of $$n$$ up to $$k$$. Now consider the algorithm for input $$n = k+1$$. We compute $$Exp(n) = Exp(k+1)$$ using the algorithm:

In the case that $$n = k+1$$ is even:

The algorithm computes $$temp = Exp(\frac{k+1}{2})$$. After this step $$temp$$ holds the correct value for $$2^{\frac{k+1}{2}}$$ because we assumed the algorithm is correct for values up to $$k$$ . The algorithm correctly returns $$temp*temp = 2^{\frac{k+1}{2}}*2^{\frac{k+1}{2}} = 2^{k+1}$$.

In the case that $$n = k+1$$ is uneven:

The algorithm computes $$temp = Exp(\frac{n-1}{2}) = Exp(\frac{k+1-1}{2}) = Exp(\frac{k}{2})$$. After this step $$temp$$ holds the correct value for $$2^{\frac{k}{2}}$$ because we assumed the algorithm is correct for values up to $$k$$ . The algorithm correctly returns $$temp*temp*2 = 2^{\frac{k}{2}}*2^{\frac{k}{2}}*2 = 2^{k+1}$$.

i.e. since $$Exp(0) = 1$$ is trivially correct by the algorithm and we showed that the algorithm is correct for $$Exp(n+1)$$ if $$Exp(n)$$ is correct; it follows that the algorithm is correct for every $$n \geq 0$$.

 Technically you also have to show that $$\frac{k+1}{2} \leq k$$ and $$\frac{k}{2} \leq k$$ for every $$k > 0$$ but that seems easy enough to prove.