Understanding loop invariants is considered an optional extension, and will be handled as a separately graded section on the quiz.

1.  int expt(int n, int k) {  // assumes k >= 0
        int n_pow_i = 1;
        int i = 0;
        // loop invariant: n_pow_i = n^i
        while (i < k) {
            n_pow_i *= n;
            i++;
        }
        // on termination, i=k, so n_pow_i = n^k
        return n_pow_i;
    }

2.  double harmonicSum(int n) { // assumes n>0
        double sum = 1;
        double denom = 1;
        // loop invariant: sum = 1 + 1/2 + 1/3 + ... + 1/denom
        while (denom < n) {
            denom += 1;
            sum += 1/denom;
        }
        // on termination, denom=n so sum = 1 + 1/2 + 1/3 + ... + 1/n
        return sum;
    }

3.  double geometricSum(int n) { // assumes n >=0
        double sum = 1;
        int k = 0;
        double denom = 1;
        // loop invariants:  sum = 1 + 1/2 + 1/4 + ... + 1/2^k
        //                   denom = 2^k
        while (k < n) {
            k++;
            denom *= 2;
            sum += 1/denom;
        }
        // on termination, k=n so sum = 1 + 1/2 + ... + 1/2^n
        return sum;
    }

4.  int mult(int j, int k) {
        if (j < 0)
            return -mult(-j,k);
        else {
            int product = 0;
            int count = 0;
            // loop invariant: product = k*count
            while (count < j) {
                product += k;
                count++;
            }
            // on termination, count=j so product=k*j
            return product;
        }
    }

5.  int sumDownBy2(int n) { //assumes n>=0
        int k = n;
        int sum = n;
        // loop invariant: sum = n + (n-2) + (n-4) + ... k
        while (k > 1) {
            k -= 2;
            sum = sum + k;
        }
        // on termination, k = 1 or 0, so
        //    sum = the sum of the positive integers n, n-2, n-4,...
        return sum;
    }

6.  int sumOdd1toN(int n) { // assumes n>0
        int sum = 1;
        int i = 1;
        // loop invariants: sum = 1 + 3 + 5 + ... + i
        //                  i is odd
        while (i+2 <= n) {
            i += 2;
            sum += i;
        }
        // on termination, i=n (if n is odd) or i=n-1 (if n is even), so
        //    sum = the sum of the odd numbers from 1 up to n
        return sum;
    }


7.  int lcm(int j, int k) { // assumes k != 0
        int guess = j;
        // loop invariant: guess is a multiple of j.
        while ((guess % k) != 0)
           guess += j;
        // on termination, guess is a multiple of k.
        // since the loop tries each multiple of j, the smallest
        // such multiple that is also a multiple of k is returned.
        return guess;
    }