1 Graphs and Trees The following two definitions of a tree are equivalent Definition 1: A tree is an acyclic graph of n vertices that has n-1 edges Definition 2: A tree is a connected graph such that Vu, v E V, there is a unique path connecting u to u. In general, when we want to show the equivalence of two definitions, we must show

1 The pulverizer We saw in lecture that the greatest common divisor(GCD)of two numbers can be written as a linear combination of them. That is, no matter which pair of integers a and b we are given, there is always a pair of integer coefficients s and t such that

Notes for recitation 5 1 Well-ordering principle Every non-empty set of natural numbers has a minimum element Do you believe this statement? Seems obvious, right? Well, it is. But dont fail to realize how tight it is. Crucially, it talks about a non-empty set -otherwise, it would clearly be false. And it also talks about natural

1 Strong Induction Recall the principle of strong induction: Principle of Strong Induction. Let(n) be a predicate. If ·P() is true,and for all n, P(O)A P(1)...A P(n) implies P(n+1), then P() is true for all n E N. As an example, let's derive the fundamental theorem of arithmetic

1 Induction Recall the principle of induction: Principle of Induction. Let P(n) be a predicate. If ·P(0) is true,an for all nE N, P(n) implies P(n+1), then P(n) is true for all nE N As an example let's try to find a simple expression equal to the following sum and then use induction to prove our guess correct 1·2+2·3+3:4+…+n·(mn+1) To help find an equivalent expression, we could try evaluating the sum for some small n and(with the help of a computer) some larger n sum

1 Logic A proposition is a statement that is either true or false. Propositions can be joined by \and\, \or\, \not\, \implies\, or \if and only if\. For each of these connective, the defini- tion and notational shorthand are given in the table below. Here A and B denote arbitrary propositions

1 Case analysis The proof of a statement can sometimes be broken down into can be tackled individually 1.1 The method In order to prove a proposition P using case analysis Write, We use case analysis Identify a sequence of conditions, at least one of which must hold. (If this is not obvious, you must prove it

1 Streaks someone tapping the H and t keys in a what felt like a random way?0 Nas the table of H's and T's below generated by flipping a fair coin 100 times

Random walks 1 Random walks a drunkard stumbles out of a bar staggers one step to the right, with a canal lies y steps to his right. Thi I equal p second, he either staggers one step to the left or probability. His home lies r steps to his left, and everal natural questions, including 1. What is the probability that the drunkard arrives safely at home instead of falling into the canal? 2. What is the expected duration of his journey however it ends? The drunkard's meandering path is called a random walk. Random walks are an im- portant subject, because they can model such a wide array of phenomena. For example

1 The Number-Picking Game Here is a game that you and I could play that reveals a strange property of expectation. 3, First, you think of a probability density function on the natural numbers. Your distri- bution can be absolutely anything you like. For example, you might choose a uniform distribution on 1, 2, ... 6, like the outcome of a fair die roll. Or you might choose a bi- probability, provided that,...,n. You can even give every natural number a non-zero nomial distribution on 0, 1 he sum of all probabilities is 1