Good resource for practice problems for inductive proofs

Question

Every year, I teach my students about using induction to prove that algorithms function as intended. My purpose, in instructing them, is to help them master the structure of the proof itself. I use simple algorithms for which we can do fairly easy inductive proofs. Here are a few examples:

Prove that arraySum will correctly compute the sum of all of the elements in arr.

public int arraySum(int[] arr){
    int k = 0;
    for (int g = 0; g < arr.length; g++)
        k = k + arr[g];
    return k;
}

Prove that this function will return $n^2$: Assume n is positive.

public int square(int n){
    int sum = 0;
    int count = 0;
    while (count < n){
        sum = sum + n;
        count = count + 1;
    }
    return sum;
}

As you can see, I am not aiming for complicated algorithms. What my students need (and what I need) is a good source for practice problems. I'd absolutely love it if they were already carefully solved (so that my students could independently study with them and check their own answers), but I could work with any source that simply has a series of pre-made reasonable practice problems.

Is there any such resource out there?

Answer 1

Any book on elementary number theory will likely have quite a few recurrences as examples and in the exercises of the early chapters. For example, the sum of the first n odd integers is $n^2$. As a recurrence this is just $n^2$ = $(n-1)^2$ + $2*n - 1$. Or possibly it will be shown as $a_n$ = $a_{n-1}$ + $2*n -1$, with $a_1$ = 1.

Some books on discrete math have many of these as well. Some even have these in summation form, rather than as recurrences.

Likewise the sum of the first n integers (start counting with 1) is $n(n+1)/2$.

From these recurrences or sums you can develop a program to give the students or have the students prove the relations and then develop the program themselves.

Even a web search for recurrence relation turns up some ideas.

A rather important sum (the geometric sum) is this: Let r be a real number and k a non-negative integer. If $r \neq 0$ then $\sum_{n=0}^k(r^n)$ = $(1 - r^{k+1})/(1-r)$.

Moreover, if $|r| < 1$ then as k increases this sum approaches 1 - r which leads to an infinite sum that is pretty comprehensible.

Also David Gries' The Science of Programming has interesting examples that he shows along with how to develop programs from pre and post conditions. The book has been mentioned in answers to other questions here also.

Answer 2

I'm using many examples involving trees (height of a tree, number of leaves, ...) or graphs (number of edges in a fully connected graph, ...). The advantage is that if I force students to draw the first three or four steps, they are usually capable of deriving the equation by themselves.