Prove that the following recursive algorithm to compute aⁿ, is correct using mathematical induction. int power(int a, int n) if (n == 0) return 1; else return a power (a, n 1);

Proof by Mathematical Induction

To prove the correctness of the recursive algorithm for computing $a^n$, we use mathematical induction.

1. Base Case (n = 0)

For $n=0$, the algorithm returns:

if (n == 0) return 1;

By definition, $a^0=1$. Thus, the base case holds: $$\text{power}(a,0)=1=a^0.$$

2. Inductive Hypothesis (n = k)

Assume that for some integer $k\ge 0$, the algorithm correctly computes $a^k$: $$\text{power}(a,k)=a^k.$$

3. Inductive Step (n = k + 1)

We must show that if the hypothesis holds for $n=k$, then it also holds for $n=k+1$.

The recursive call for $n=k+1$ is:

power(a, k + 1) = a * power(a, k).

By the inductive hypothesis, $\text{power}(a,k)=a^k$. Substituting: $$\text{power}(a,k+1)=a\cdot a^k=a^{k+1}.$$ Thus, the algorithm correctly computes $a^{k+1}$.

Conclusion

By the principle of mathematical induction, the algorithm computes $a^n$ correctly for all non-negative integers $n$.

// The algorithm works by:
// 1. Returning 1 when n = 0 (base case).
// 2. Recursively multiplying a by power(a, n-1) for n > 0.