Recursion (Cont.)
Algorithms  CS2500  25 January 2018
Proofs
A proof is a sequence of steps to get from a hypothesis to a conclusion
Counterexamples
An example that proves a certain point is wrong.
###The principle of Recursion Definition: A property P on a domain D is a function P that accepts inputs from the domain D and returns a Boolean value. If P is a property on D, and d is in D then we say that P holds for d if P(d) is true, P does not hold for d if P(d) is false
Ex: D is the set of all cars and P is a property “is blue”
The Six Steps:
 Define the Problem
 Check Stopping Values + Two More
 Check that Recursion Stays in D
 Check that Recursion Halts
 Check Inheritance
 Conclude the proof
Step 1. Define the Problem
 Define the Domain D: clearly state what objects you are dealing with – numbers, trees, Tower of Hanoi disks, etc.
 Provide names and definitions for all functions you will be talking about
 You can often use Python for the definitions
 Look carefully for anomalies such as division by 0
 State clearly what you are trying to prove.
Step 2. Check the Stopping Values and Two Other Values
 Checking that whatever you are trying to prove is required for the stopping values, but optional for the two other values
 We do the two other values because we want to reduce the likelihood of having made a mistake
 If you fail, go back to Step 1.
Step 3. Prove that Recursion Stays in D
 If you fail, go back to Step 1.
Step 4. Prove that Recursion Halts
 Don’t trace the recursion
 We use the Counting Strategy
 Assign a nonnegative integer as a counter to every value in the domain D. If whenever recursion is triggered, the counters associated with called values are < the value associated with the calling value, recursion will halt!
 If you fail, go back to Step 1.
Step 5. Check that P is Inherited Recursively
 This is often the hard part
 You may assume that P is true for all values called recursively.
 If you fail, go back to Step 1.
Step 6. Invoke the Principle of Recursion
 Clearly indicate that you have finished the proof.
Equivalent Functions
 How can you tell that 2 functions are always equivalent?
Example Proof:
 Domain D: All natural numbers; P(n) is true if f1(n) = f2(n); We want to prove that for any natural number n, P(n) is true.
 Check the values

 Use the counting strategy. Use n as the counter, the counter decreases, and done.
 Statement: f2(n) = n + f2(n1); f2(n) = n + f1(n1); f2(n) = n + n*(n1)/2; n*(1 + (n1)/2); n*(2 + (n1))/2; n*(n+1)/2; f1(n); Therefore: f2(n) = f1(n)
Modulo
 P mod Q is always between 0 and Q1 (assuming P and Q are positive integers)
 (P+R) mod Q = P mod Q+R mod Q