Good resource for practice problems for inductive proofs
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| &lt; 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.