UA MATH 294A - Induction (3 pages)

Previewing page 1 of 3 page document View the full content.
View Full Document

Induction



Previewing page 1 of actual document.

View the full content.
View Full Document
View Full Document

Induction

17 views

Lecture Notes


Pages:
3
School:
University of Arizona
Course:
Math 294a - Problem-Solving Laboratory
Problem-Solving Laboratory Documents

Unformatted text preview:

Induction Tal Sutton September 18 2006 Induction Let P x be a statement about x In order to show that P n is eventually true for all possible integers n greater than some starting point a one can proceed as follows The first case Show there is some integer a such that P a is true The Inductive Hypothesis Assume the statement is true for integers up to k a on down to the first case P a The Inductive Step Prove that the next case P k 1 is true using the first case and the Inductive Hypothesis Example 1 Prove for all n 1 12 22 n2 n n 1 2n 1 6 Example 2 If V E and F represent respectively the number of vertices edges and faces of a connected planar graph then V E F 2 Example 3 Use induction to show that for all n 0 that n5 n4 n3 n Z 5 2 3 30 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 Fk denote the kth Fibonacci number prove 2 Fn 1 Fn2 F2n 1 Problem 1 If an is a sequence such that for n 1 2 an an 1 1 what happens to an as n tends towards infinity Problem 2 Use induction to prove that there are exactly 2n subsets of a set containing n elements Problem 3 Show that every number in the following sequence is divisible by 53 1007 10017 100117 1001117 Problem 4 Suppose n coins are given named C1 C2 Cn For each k Ck is 1 of falling heads If the biased so that when tossed it has probability 2k 1 n 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 1r is an integer Prove that rn is an integer for every positive integer n 1 rn Problem 6 Let a1 a2 an be a permutation of the set Sn 1 2 n An element i in Sn is called a fixed point of this permutation if ai i 1 A derangement of Sn is a permutation of Sn having no fixed points Let gn denote the number of derangements of Sn Show that g1 0 g2 1 and gn n 1 gn 2 gn 1 for n 2 2 Let fn be



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Induction and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Induction and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?