Discrete Mathematics: Elementary and Beyond

4.3 A Formula for the Fibonacci Numbers 71 valuesAandBas parameters). E 0 =A, E 1 =B, E 2 =A+B, E 3 =B+(A+B)=A+2B, E 4 =(A+B)+(A ...

72 4. Fibonacci Numbers 4 3 2 1 8·8 = 64 1 2 3 4 5·13 = 65 FIGURE 4.1. Proof of 64 = 65. Proof.It is straightforward to check th ...

4.3 A Formula for the Fibonacci Numbers 73 translates into c·qn+1=c·qn+c·qn−^1 , which after simplification becomes q^2 =q+1. So ...

74 4. Fibonacci Numbers where the term we ignore is less than^12 ifn≥2 (and tends to 0 ifntends to infinity); this implies thatF ...

4.3 A Formula for the Fibonacci Numbers 75 4.3.12Consider a sequence of numbersb 0 ,b 1 ,b 2 ,...such thatb 0 =0,b 1 =1, andb 2 ...

This page intentionally left blank ...

5 Combinatorial Probability 5.1 Events and Probabilities.................... Probability theory is one of the most important are ...

78 5. Combinatorial Probability the subsetL={ 4 , 5 , 6 }⊆Scorresponds to the event that we throw a number larger than 3. The in ...

5.2 Independent Repetition of an Experiment 79 5.2 Independent Repetition of an Experiment Let us repeat our experimentntimes. W ...

80 5. Combinatorial Probability E={ 2 , 4 , 6 }is the event that the result of throwing a dice is even, and T={ 3 , 6 }is the ev ...

5.3 The Law of Large Numbers 81 Theorem 5.3.1Fix an arbitrarily small positive number.Ifweflipa coinntimes, the probability tha ...

82 5. Combinatorial Probability the probability that the number of heads is less thanm−tor larger than m+tless than 0.05. By The ...

5.4 The Law of Small Numbers and the Law of Very Large Numbers 83 By (3.9), this can be bounded from above by 22 m−^1 e−t (^2) / ...

84 5. Combinatorial Probability argument, or a provable special case). A theorem, of course, needs much more: an exact proof. Th ...

5.4 The Law of Small Numbers and the Law of Very Large Numbers 85 5.4.5We flip a coinntimes (n≥1). For which values ofnare the f ...

This page intentionally left blank ...

6 Integers, Divisors, and Primes In this chapter we discuss properties of integers. This area of mathematics is callednumber the ...

88 6. Integers, Divisors, and Primes 6.1.1Check (using the definition) that 1|a,− 1 |a,a|aand−a|afor every integera. 6.1.2What d ...

6.2 Primes and Their History 89 1, 2 , 3 ,4, 5 ,6, 7 ,8,9,10, 11 , 12, 13 , 14, 15, 16, 17 , 18, 19 , 20, 21, 22, 23 , 24, 25, 2 ...

90 6. Integers, Divisors, and Primes 0 200 400 600 800 1000 FIGURE 6.1. A bar chart of primes up to 1000. tation, thatit is uniq ...