Math 55 - Fall 2007 - Lecture notes # 17 - Oct 8 (Monday)Read section 4.1 - 4.4, on inductionGoals for today: Begin InductionProof by induction: a technique for proving theorems like"FORALL positive integers n, P(n)"(and more general problems later)EX: FORALL positive integers n,the sum of the first n integers is n*(n+1)/2i.e. "sum_{i=1}^n i = 1+2+3+...+n = n*(n+1)/2" is P(n)EX: FORALL positive integers n,the sum of the first n odd integers is n^2,i.e. "sum_{i=1}^n (2*i-1) = 1+3+5+...+(2*n-1) = n^2" is P(n)Basic idea: Prove P(1) is true directlyEX: P(1) means "1=1^2", which is trueThen show that all of the implicationsP(1)->P(2),P(2)->P(3),..., P(n)->P(n+1),... are true for all nThen starting from P(1) which we know to be true, P(m) is true forall larger integers m, because P(1)->P(2)-> ... -> P(m)I.e. need to prove an infinite number of tiny theorems; butcan do them all at once by showing that P(n)->P(n+1) istrue no matter what the integer n is:EX: P(n) means that "sum_{i=1}^n (2*i-1) = n^2"Show that if P(n) is true, and then P(n+1) is true, i.e.that sum_{i=1}^{n+1} (2*i-1) = (n+1)^2.To do this we suppose that P(n) is true, i.e. thatsum_{i=1}^n (2*i-1) = n^2and add 2*(n+1)-1 to both sides to getsum_{i=1}^{n+1} (2*i-1) = n^2 + 2*(n+1)-1= n^2 + 2*n + 1 = (n+1)^2so P(n+1) is also true as desired.Here is another way to understand induction. Suppose you hadproven both P(1) and P(n) -> P(n+1) for positive integers n.How could P(m) ever be false? Let’s suppose P(m) is false forsome positive m and find a contradiction. LetF = {m : P(m) is false}1i.e. the set of all positive integers m for which P(m) is false.Then F must obviously have a smallest entry, call it m0.So P(m0) is false, but P(n) is true for n<m0. How can this be?We can’t have m0=1, because we started with P(1) being true.And we can’t have m0>1, because then P(m0-1) is true, andP(m0-1) -> P(m0), a contradiction.In addition to using induction to prove equalities, we can proveinequalities:EX: Prove 2^n < n! if n>= 4; P(n) = "2^n < n!"Base case: P(4) means we have to confirm that 2^4=16<24=4!Induction step: Suppose P(n) is true, i.e. 2^n < n!. This impliesthat 2*2^n < 2*n!, or 2^(n+1) < 2*n! < (n+1)*n! < (n+1)! as desired.Note that we don’t have to start induction at n=1.EX: Prove G = sum_{i=0}^n r^i = (1-r^(n+1))/(1-r), if r != 1.We proved this earlier using a different idea (computing r*G-G)but here we use induction.P(n) = "sum_{i=0}^n r^i = (1-r^(n+1))/(1-r)"Base case: P(0): sum_{i=0}^0 r^i = 1 = (1-r)/(1-r)Induction step: Suppose P(n) is true, and confirm P(n+1):sum_{i=0}^{n+1} r^i = sum_{i=0}^{n} r^i + r^(n+1)= (1-r^(n+1))/(1-r) + r^(n+1) by P(n)= ( 1-r^(n+1) + (1-r)*r^(n+1) )/(1-r)= ( 1-r^(n+1) + r^(n+1) - r^(n+2) )/(1-r)= ( 1 - r^(n+2) )/(1-r)which proves P(n+1).Another way to use the induction idea: show that if the result is truefor all "smaller" problems 1,2,3,...,n, then it is true forthe next bigger one (n+1), orP(1) and P(2) and ... and P(n) -> P(n+1)The book calls this "strong induction."EX: Every positive integer >= 2 can be written as the product of primesP(k) = "k can be written as product of primes"Base case: P(2) is trueInduction step: Now suppose P(2),...,P(n) are true. Consider n+1:Case 1: n+1 prime: doneCase 2: n+1 composite, say n+1 = a*b where a>1, b>1.2Then a = (n+1)/b < n+1 and b = (n+1)/a < n+1. SoP(a) and P(b) are true by induction, and thus n+1 can bewritten as the product of sets of prime factors of a and of b.EX: Show every amount of postage of 12 cents or more can beformed used only 4 and 5 cent stampsProof:P(m) = "can form postage of m cents out of 4 and 5 cent stamps"Base case:P(12) true, since 12=3*4+0*5P(13) true, since 13=2*4+1*5P(14) true, since 14=1*4+2*5P(15) true, since 15=0*4+3*5Induction step: Suppose P(12),...,P(n), true, where n>=15.Since n>=15, n-3>=12 so P(n-3) is true. Then to show P(n+1),use postage for P(n-3) plus a 4 cent stamp.EX: So far we have been doing induction on numbers, showing P(n)is true if P(k) is true for numbers k smaller than n. But wecan also do induction on other structures besides numbers, suchas data structures that come up in programs. We illustrate witha structure called a tree, which is a special case of a graph.DEF A graph G = (V,E) consists of a nonempty set V of vertices,and a set E of edges connecting them. More formally, if a inV and b in V are vertices, then (a,b) in E means that thereis an edge connecting a,bEX: G = (V,E), V = {a,b,c,d}, E = {(a,b),(b,c),(c,d),(d,a),(a,c)}DEF a path from node a to node c is a set of edges connectedend to end starting at a and ending at cEX: G as before, path from a to d consists of edges (a,c),(c,d)EX: Other common graphs, questions people ask about themV = {cities}, E = {roads connecting them};3what are shortest paths from one city to another?V = {computers}, E = {networks connecting them},what is available bandwidth for any two computers to communicate?V = {web pages}, E = {Whether one points to another}what is best answer to a web search?V = {people}, E = {Whether one person has met another}what is likely path of spread of disease?ASK&WAIT: Other examples?DEF A tree is a graph with exactly one path between any two nodes.A rooted tree is a tree with a distinguished node called arootASK&WAIT: Is G a tree?ASK&WAIT: Where is the root of Tree 2 above?Thm: if I remove the root from a tree T, and its k connecting edges,I am left with k unconnected subtrees T1,...,Tk (ie there is nopath from any node in Ti to any node in Tj)ASK&WAIT: what are k connected subtrees in figure above?Proof: let r1,...,rk be the nodes connected to the root.I need to show 2 things: that each Ti is unconnected toany other, and each Ti is a tree.I use proof by contradiction: suppose nodea in Ti and node b in Tj were connected; I will find a4contradiction. Since a is connected to r and b is connectedto r in T, there must be two paths from a to r in T(the one directly from a to r and the one via b);this contradicts the fact that T is a tree.Now suppose that Ti is not a tree; I will find anothercontradiction. Ti not a tree means there are two nodesc and d in Ti with either 0 or >1 paths connecting them.If there are >1 paths connecting them in Ti, the samepaths exist in T, so T must not be a tree. If there areno paths connecting them in Ti, then there are inparticular no paths connecting them both to ri, and henceno paths in T connecting both to root; contradicting thefact that T was a tree.Thm: Let T be any tree. Let E be the number of