<p>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. </p>

CC BY-SA 4.0
2018-10-26T14:50:42.240Z
2018-10-26T14:50:42.240Z
OBu
<p>Any book on elementary number theory will likely have quite a few <em>recurrences</em> 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. </p>

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

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

<p>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. </p>

<p>Even a web search for recurrence relation turns up some ideas. </p>

<p>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)$.  </p>

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

<p>Also David Gries' <a href="https://rads.stackoverflow.com/amzn/click/038790641X" rel="nofollow noreferrer"><em>The Science of Programming</em></a> 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. </p>

CC BY-SA 3.0
2017-10-23T20:02:17.957Z
2017-10-24T00:01:21.030Z
2017-10-24T00:01:21.030Z
Buffy
<p>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:</p>

<p><strong>Prove that <code>arraySum</code> will correctly compute the sum of all of the elements in <code>arr</code></strong>.</p>

<pre><code>public int arraySum(int[] arr){
    int k = 0;
    for (int g = 0; g &lt; arr.length; g++)
        k = k + arr[g];
    return k;
}
</code></pre>

<p><strong>Prove that this function will return <span class="math-container">$n^2$</span>:  Assume n is positive.</strong></p>

<pre><code>public int square(int n){
    int sum = 0;
    int count = 0;
    while (count &lt; n){
        sum = sum + n;
        count = count + 1;
    }
    return sum;
}
</code></pre>

<p>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.</p>

<p>Is there any such resource out there?</p>

<resource-request><induction>
Good resource for practice problems for inductive proofs
# Good resource for practice problems for inductive proofs

(Asked by: username_0 on 2017-10-23)

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?

**Tags:** resource-request, induction


---

## 2 answers

### Answer by username_2 on 2017-10-23. Score: 2

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*](https://rads.stackoverflow.com/amzn/click/038790641X) 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 by username_1 on 2018-10-26. Score: 1

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.


---

