Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-10-26T14:50:42.240Z
Answers.LastActivityDate: 2018-10-26T14:50:42.240Z
Answers.UserDisplayName: OBu
Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-10-23T20:02:17.957Z
Answers.LastActivityDate: 2017-10-24T00:01:21.030Z
Answers.LastEditDate: 2017-10-24T00:01:21.030Z
Answers.UserDisplayName: Buffy
Body: <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>
  
Tags: <resource-request><induction>
Title: Good resource for practice problems for inductive proofs
ThreadText: # 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.
  
  
  ---
  
  