CISC 102 Lecture Notes - Lecture 12: Mathematical Induction, Injective Function, Bijection

• School: Queen's University
• Department: Computing
• Course: CISC 102
• Professor: D. Rappaport

Document Summary

We can define n! and (n+1)! using these explicit iterative formulae: n! This is a recursive definition of the factorial function. The factorial function is defined for non-negative integers, that is {0,1,2,3, } as follows: (i) (ii) if n > 0 then n! = n x (n-1)! (recursive definition) (internal way of defining things) We can use a recursive definition for the handshake problem! Suppose that s is a set consisting of n elements, n 2. How many two-element subsets are there of the set. Need a base statement and a recursive definition. The recursive definition is based on the observation that a set of n elemetns has n-1 more two-element subsets than a set of n-1 elements. Let f be a fn w domain {2,3,4, } and range , such that: In other words: n , n 2 i. ii. f(2) = 1 (1 two-element subset) f(n) = f(n-1) + n-1 f (n) = n(n 1)/2.