Proof by induction - algorithm

Question

I need some help to sort out if my answer is right for this question. The algorithm calculates $x^n$.

Question: Argue the correctness of the algorithm using proof by induction.

Note: Even if you haven't managed to complete the previous proof, assume that expIterative(x, n) has been proven to be correct for any x ∈ R and n >= 0. Furthermore, remember that integer divison always rounds off toward 0, and consider the two cases when n is odd and when n is even. A proof by induction is most appropriate for this algorithm.

double expRecursive(double x, int n) {
    if (n <= 4) {
        return expIterativ(x, n);
    }

    return expRecursive(x, n/2) *
           expRecursive(x, (n + 1)/2);
}

My answer:

Base Case:

We can from the note assume that it works for $n = 4$.

Inductive case:

Assume that is works for n = k: $expRecursive(x, \frac{k}{2}) \times expRecursive(x, \frac{k+1}{2}) = x^k$

Than show that it also works for $n = k + 1$:

FOR ODD N:

$expRecursive(x, \frac{k+1}{2}) \times expRecursive(x, \frac{k+2}{2}) = expRecursive(x, \frac{k+1}{2}) \times expRecursive(x, \frac{k+1}{2}) = x^{\frac{k+1}{2}} \times x^{\frac{k+1}{2}} = x^{k+1}$

FOR EVEN N:

$expRecursive(x, \frac{k+1}{2}) \times expRecursive(x, \frac{k+2}{2}) = expRecursive(x, \frac{k}{2}) \times expRecursive(x, \frac{k+2}{2}) = x^{\frac{k}{2}} \times x^{\frac{k+2}{2}} = x^{k+1}$

Is this the correct way to do it or how should I do it?

Answer 1

The proof is correct. The if-else statement

if (n <= 4) {
    return expIterativ(x, n);
}

corresponds to the base case.

The induction hypothesis has been correctly stated.

The inductive step

return expRecursive(x, n/2) 
       expRecursive(x, (n + 1)/2);

is based on dividing $n=k+1$ into two cases according to its parity. The logic in your proof is good.

Remarks: It's likely that you've omitted a * in your code.

return expRecursive(x, n/2) * expRecursive(x, (n + 1)/2);