CSE115/ENGR160 Discrete Mathematics 04/03/125.3 Recursive definitions and structural inductionRecursive definitionsRecursively defined functionsExampleSlide 6Recursive functionsSlide 8Slide 9Example – Fibonacci numbersSlide 11Slide 12Recursively defined sets and structuresStringSlide 15ConcatenationLength of a stringWell-formed formulaeRooted treesSlide 20Binary treesExtended binary treesSlide 23Full binary treesFull binary treeStructural inductionSlide 27Slide 28Trees and structural inductionHeight of binary treeNumber of vertices in a binary treeTheoremSlide 33CSE115/ENGR160 Discrete Mathematics04/03/12Ming-Hsuan YangUC Merced15.3 Recursive definitions and structural induction2A recursively defined pictureRecursive definitions•The sequence of powers of 2 is given by an=2n for n=0, 1, 2, …•Can also be defined by a0=1, and a rule for finding a term of the sequence from the previous one, i.e., an+1=2an•Can use induction to prove results about the sequence•Structural induction: We define a set recursively by specifying some initial elements in a basis step and provide a rule for constructing new elements from those already in the recursive step3Recursively defined functions•Use two steps to define a function with the set of non-negative integers as its domain•Basis step: specify the value for the function at zero•Recursive step: give a rule for finding its value at an integer from its values at smaller integers•Such a definition is called a recursive or inductive definition4Example•Suppose f is defined recursively by–f(0)=3–f(n+1)=2f(n)+3Find f(1), f(2), f(3), and f(4)–f(1)=2f(0)+3=2*3+3=9–f(2)=2f(1)+3=2*9+3=21–f(3)=2f(2)+3=2*21+3=45–f(4)=2f(3)+3=2*45+3=935Example•Give an inductive definition of the factorial function f(n)=n!•Note that (n+1)!=(n+1)∙n!•We can define f(0)=1 and f(n+1)=(n+1)f(n)•To determine a value, e.g., f(5)=5!, we can use the recursive function f(5)=5∙f(4)=5∙4∙f(3)=5∙4∙3∙f(2)=5∙4∙3∙2∙f(1) =5∙4∙3∙2∙1∙f(0)=5∙4∙3∙2∙1∙1=1206Recursive functions•Recursively defined functions are well defined•For every positive integer, the value of the function is determined in an unambiguous way•Given any positive integer, we can use the two parts of the definition to find the value of the function at that integer•We obtain the same value no matter how we apply two parts of the definition7Example•Given a recursive definition of an, where a is a non-zero real number and n is a non-negative integer•Note that an+1=a∙an and a0=1•These two equations uniquely define an for all non-negative integer n8Example•Given a recursive definition of• The first part of the recursive definition•The second part is 9nkka0000aakknknknkkaaa0110)(Example – Fibonacci numbers•Fibonacci numbers f0, f1, f2, are defined by the equations, f0=0, f1=1, and fn=fn-1+fn-2 for n=2, 3, 4, …•By definition f2=f1+f0=1+0=1 f3=f2+f1=1+1=2 f4=f3+f2=2+1=3 f5=f4+f3=3+2=5 f6=f5+f4=5+3=810Example•Use strong induction to show when n≥3, fn>�n-2 where fn is a Fibonacci number and •Let p(n) be the proposition that fn>�n-2 •Basis step: note that so that p(3) and p(4) are true•Inductive step: assume p(j) is true, i.e., fj>�j-2 with 3≤j ≤k where k≥4. We need to show that p(k+1) is true, i.e., fk>�k-2 112/)51( 42332/)53(,2 ff Example•First note that is a solution to x�2-x-1=0, so �2+1, thus=�•By inductive hypothesis, if k≥4, it follows fk-1>�k-3 , fk>�k-2 •So, It follows that p(k+1) is true. This completes the proof 12323321)1(kkkkk13211kkkkkkfffRecursively defined sets and structures•Consider the subset S of the set of integers defined by–Basis step: 3∊S–Recursive step: if x∊S and y∊S, then x+y∊S•The new elements formed by this are 3+3=6, 3+6=9, 6+6=12, …•We will show that S is the set of all positive multiples of 3 (using structural induction)13String•The set ∑* of strings over the alphabet ∑ can be defined recursively by–Basis step: ∊∑* (where is the empty string containing no � �symbols)–Recursive step: if w∊∑* and x∊∑ then wx ∊∑*•The basis step defines that the empty string belongs to string•The recursive step states new strings are produced by adding a symbol from ∑ to the end of stings in ∑*•At each application of the recursive step, strings containing one additional symbol are generated14Example•If ∑={0, 1}, the strings found to be in ∑*, the set of all bit strings, are •�, specified to be in ∑* in the basis step•0 and 1 found in the 1st recursive step•00, 01, 10, and 11 are found in the 2nd recursive step, and so on15Concatenation•Two strings can be combined via the operation of concatenation•Let ∑ be a set of symbols and ∑* be the set of strings formed from symbols in ∑•We can define the concatenation for two strings by recursive steps–Basis step: if w∊∑*, then w =w, where is the empty ∙� �string–Recursive step: If w1∊∑*, w2∊∑* and x ∊∑, then w1 ∙ (w2 x)=(w1 ∙ w2)x–Oftentimes w1 ∙ w2 is rewritten as w1w2–e.g., w1=abra, and w2=cadabra, w1w2=abracadabra16Length of a string•Give a recursive definition of l(w), the length of a string w•The length of a string is defined by–l( )=0�–l(wx)=l(w)+1 if w∊∑* and x∊∑ 17Well-formed formulae•We can define the set of well-formed formulae for compound statement forms involving T, F, proposition variables and operators from the set {┐, , , →, ˄ ˅ ↔}•Basis step: T, F, and s, where s is a propositional variable are well-formed formulae•Recursive step: If E and F are well-formed formulae, then ┐E, E F, E F, E→F, E˄ ˅ ↔F are well-formed formulae•From an initial application of the recursive step, we know that (p q), (p→F), (F→q) and (q F) are well-formed formulae˅ ˄•A second application of the recursive step shows that ((p q) ˅→(q F)), (q (˄ ˅ p q)), and ((p→F)→T) are well-formed formulae˅18Rooted trees•The set of rooted trees, where a rooted tree consists of a set of vertices containing a distinguished vertex called the root, and edges connecting these vertices, can be defined recursively by–Basis step: a single vertex r is a rooted tree–Recursive step: suppose