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

The expectation or expected value of a random variable is a single number that tells you a lot about the behavior of the variable. Roughly, the expectation is the average value, where each value is weighted according to the probability that it comes up. Formally, the expected value of a random variable r defined on a sample space s is: (B)=∑R()Pr(o) To appreciate its signficance, suppose S is the set of students in a class, and we select a student uniformly at random. Let r be the selected student's exam score. Then

Random variable Weve used probablity to model a variety of experiments, games, and tests. Through out, we have tried to compute probabilities of events. We asked for example, what is the probability of the event that you win the Monty Hall game? What is the probability of the event that it rains

1 Independent Events Suppose that we flip two fair coins simultaneously on opposite sides of room. Intu- itively, the way one coin lands does not affect the way the other coin lands. The mathe- matical concept that captures this intuition is called independence. In particular, events A and B are independent if and only if:

Introduction to Probability Probability is the last topic in this course and perhaps the most important. Many Igorithms rely on randomization. Investigating their correctness and performance re- quires probability theory. Moreover, many aspects of computer systems, such as memory