Iterative processes are proven using loop invariants, and recursive processes are proven using induction. In some cases it might be trickier to find a good loop invariant, where proving recursive processes is just to follow the very own definitions of the process.

---

Consider the following recursive definition:

maxList [x] = x
maxList (x:xs) = max(x, maxList xs)

We can prove its correctness using induction:

– Base case: Max element of a list of size 1 is the element itself.

– Inductive step: Assume that maxList of xs is maximum element.

Then for maxList (x:xs) we have 2 cases:
1. maxList of xs is >= x, in which case we select maxList xs
2. x is >= maxList xs, in which case we select x
In either case, we pick the larger element which will be the maximum.

---

Now consider the following iterative definition:

var max = x[0], i;

for (i = 0; i < x.length; i++) {
     if (x[i] >= max) max = x[i];
}

In this case we need to find a loop invariant to use that will hold pre-, during, and post- processing of that code block.

We can use the following loop invariant: max is the biggest element in the subarray x(0, i).

– Before loop: for array of size 1 we have the same element to be maximum. So the loop invariant holds.

– Within the loop, we have two cases:
1. x[i] >= max, in which we set max to be x[i]
2. x[i] < max, in which we don't change max
In either case, the loop invariant holds.

– After loop: max is the biggest element in the subarray x(0, x.length – 1) which is just x.

Consider the following task:
Print the first 100 squares using at most one loop. The constraints are that you are not allowed to use multiplication or functions.

To tackle this one, we will have to use one interesting property of the squares that I noticed while taking my kid to school. At the school, there was a table with all natural numbers listed from 1 to 100. While looking at it, I noticed the distances between the squares kept increasing by 2k + 1 for every kth square.

So for example, from 1 to 4 (the first square), the distance is 3. Since this is the first square, k = 1 so 2*1 + 1 = 3. The distance from 4 to 9 (the second square) is 5. Since this is the second square, k = 2 so 2*2 + 1 = 5. And so on.

Naturally I tried to generalize this and came to the following recurrent relation:

Before we use this relation in our program, we will first prove its correctness.

We will prove that by induction.

The base case is which is true. Now, we assume that . If we add to both sides, we get . Thus the identity is proven.

Now, here is our simple program:

var s = 1;
for (var i = 1; i <= 100; i++) {
    console.log(s);
    s += i + i + 1;
}