Guessing a particular solution. Recall that a general linear recurrence has the form: f(n)=a1f(n-1)+a2f(n-2)+…+aaf(n-d)+g(n) As explained in lecture, one step in solving this recurrence is finding a particular solu- tion; i.e., a function f(n)that satisfies the recurrence, but may not be consistent with the boundary conditions. Here's a recipe to help you guess a particular solution:

1 Sums and approximations Problem 1. Evaluate the following sums Solution. The formula for the sum of an infinite geometric series with ratio 1 /2

1 RSA In 1977, Ronald Rivest, Adi Shamir, and Leonard Adleman proposed a highly secure cryp- tosystem(called RSa)based on number theory. Despite decades of attack, no significant weakness has been found (Well, none that you and me would know.)Moreover, RSA has a major advantage over traditional codes: the sender and receiver of an encrypted

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

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

Conditional Probability Suppose that we pick a random person in the world. Everyone has an equal chance of being selected. Let A be the event that the person is an MIT student, and let B be the event that the person lives in Cambridge. What are the probabilities of these events? Intuitively

Generating functions Generating functions are one of the most surprising, useful, and clever inventions in discrete math. Roughly speaking, generating functions transform problems about se- quences into problems about functions. This is great because weve got piles of mathe- matical machinery for manipulating functions. Thanks to generating functions, we can

We realize everyone has been working pretty hard this term, and were considering Warding some prizes for truly exceptional coursework. Here are some possible categories Best Administrative Critique We asserted that the quiz was closed-book. On the cover

In this example, the domain is the set fa,b, c, d, el and the range is the set Y= (1, 2, 3, 4, 5/. Related elements are joined by an arrow. This relation is a function because every element on the left is related to exactly one element on the right. In graph-theoretic

1 Introduction normally, a graph is a bunch of dots connected by lines. Here is an example of a graph