### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Class Note for MATH 294A with Professor Savitt at UA 2

### View Full Document

## 17

## 0

## Popular in Course

## Popular in Department

This 3 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Arizona taught by a professor in Fall. Since its upload, it has received 17 views.

## Reviews for Class Note for MATH 294A with Professor Savitt at UA 2

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 02/06/15

Induction Tal Sutton September 18 2006 Induction Let Pz be a statement about x In order to show that Pn is eventually true for all possible integers 71 greater than some starting point a one can proceed as follows 0 The rst case Show there is some integer a such that P a is true 0 The Inductive Hypothesis Assume the statement is true for integers up to k 2 a on down to the rst case Pa o The Inductive Step Prove that the next case Pk 1 is true using the rst case and the Inductive Hypothesis Example 1 Prove for all n 2 1 12 1 1222n2w Example 2 If V E and F represent respectively the number of vertices edges and faces of a connected planar graph then V7EF2 Example 3 Use induction to show that for all n 2 0 that n3 71 iii Z 3 306 n5 n4 E 3 Example 4 Recurrence A fair coin is tossed n times What is the probability that two heads appear in succession somewhere in the sequence of throws Example 5 General Induction Let F denote the kth Fibonacci number prove F3 F F2nr Problem 1 If an is a sequence such that for n 2 1 2 7 away 1 what happens to an as 71 tends towards in nity Problem 2 Use induction to prove that there are exactly 2 subsets of a set containing 71 elements Problem 3 Show that every number in the following sequence is divisible by 53 1007100171001171001117 Problem 4 Suppose 71 coins are given named 01 OZ On For each k 0 is biased so that when tossed it has probability 2 of falling heads If the 71 coins are tossed what is the probability that the number of heads is odd Express the answer as a rational function of n Putnam 2001 Problem 5 Let r be a number such that r i is an integer Prove that r 7 is an integer for every positive integer 71 Problem 6 Let a1 a2 an be a permutation of the set Sn 1 2 n An element 239 in Sn is called a xed point of this permutation if a 239 1 A derangement of Sn is a permutation of Sn having no xed points Let 9 denote the number of derangements of Sn Show that 910 921 and 9 n 71g2 gn1 form gt 2 2 Let f be the number of permutations of Sn with exactly 1 xed point Show that fn 7 gn 1 Problem 7 Let P denote the number of regions formed when 71 lines are drawn in the Euclidean plane in such a way that no three lines meet at one point and no two lines are parallel Come up with a recurrence relation for P and prove that it holds for all n 2 1 Problem 8 Prove the arithmetic mean geometric mean inequality which states for al an all positive real numbers that a1an n sue 2a1an Problem 9 Let n be a positive integer and a 2 1 for 239 1 2 n Show that n 1 1a11a21an2 n 1a1a Problem 10 Let F be the kth Fibonacci number prove for all positive integers F 7 1 1 V5 1 7 VS 7 2 2 Problem 11 Suppose a1 an and b1 bn are real numbers prove Zqai 1 2 Zak 2121 k1 k1 k1 Problem 12 Show that for n 2 6 a square can be dissected into 71 smaller squares not necessarily all of the same size

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.