Advanced High-School Mathematics

SECTION 2.1 Elementary Number Theory 91 The coefficients are called the (decimal)digits. Arguably the second-most popular number ...

92 CHAPTER 2 Discrete Mathematics Example 3. The representation of 11111 in trinary would require 9 trinary digits since log 311 ...

SECTION 2.1 Elementary Number Theory 93 2.1.9 Linear recurrence relations Many, if not most reasonably serious students have hea ...

94 CHAPTER 2 Discrete Mathematics For certain values of k, the above sequence can exhibit some very strange—even chaotic—behavio ...

SECTION 2.1 Elementary Number Theory 95 note, however that the difference equations leading to arithmetic se- quences (un+1−un= ...

96 CHAPTER 2 Discrete Mathematics Quadratic—distinct factors over the reals. Next, assume that our polynomialC(x) is quadratic; ...

SECTION 2.1 Elementary Number Theory 97 Finally, one can show thatanysolution of (2.4) is of the form given in (2.5). We won’t b ...

98 CHAPTER 2 Discrete Mathematics 0 = u 0 =A 120 +A 2 (−1)^0 =A 1 +A 2 1 = u 1 =A 121 +A 2 (−1)^1 = 2A 1 −A 2 all of which impli ...

SECTION 2.1 Elementary Number Theory 99 un+2 = −un+1−un, n= 0, 1 , 2 ,..., since the characteristic polynomialC(x) =x^2 +x+ 1 is ...

100 CHAPTER 2 Discrete Mathematics That is to say, the real and imaginary parts of (a+bi)nare cosnθ and sinnθ, whereθ is as abov ...

SECTION 2.1 Elementary Number Theory 101 However, given thatu 0 = 0, u 1 = 1, we get 0 = A 1 = Acos 2 π 3 +Bsin 2 π 3 =− A 2 + √ ...

102 CHAPTER 2 Discrete Mathematics higher-order differences. The arithmetic sequences have con- stant first-order differences; i ...

SECTION 2.1 Elementary Number Theory 103 Such difference equations can be solved in principle; in fact the gen- eral solution of ...

104 CHAPTER 2 Discrete Mathematics Finally, we seta 0 =u 0 and use the fact that un+1=un+vn to check that un=aknk+ak− 1 nk−^1 +· ...

SECTION 2.1 Elementary Number Theory 105 a(n+ 2)^2 − 2 a(n+ 1)^2 +an^2 = 1, which quickly reduces to 2a = 1, soa=^12. Next, we f ...

106 CHAPTER 2 Discrete Mathematics Solve the Fibonaccidifference equation un+2=un+1+un, n = 0 , 1 , 2 ,...whereu 0 =u 1 = 1. Le ...

SECTION 2.1 Elementary Number Theory 107 Solve the inhomogeneous linear difference equation un+3− 3 un+2+ 3un+1−un= 2, n= 0, 1 ...

108 CHAPTER 2 Discrete Mathematics (b) Using part (a) show that ∑k l=0 Ñ k l é (−1)llk = (−1)kk! (Hint: this can be shown using ...

SECTION 2.2 Elementary Graph Theory 109 (Just do the long multiplication showing that (1−x−x^2 ) Ñ∞ ∑ k=1 Fkxk é =x. This says t ...

110 CHAPTER 2 Discrete Mathematics Other definitions are as follows. An edge is called aloopif it joins a vertex to itself (see ...