## Induction

Previewing page *1*
of
actual document.

**View the full content.**View Full Document

## Induction

0 0 17 views

Lecture Notes

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

**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