Discrete Mathematics: Elementary and Beyond

16 Answers to Exercises 1 Let’s Count! 1.1 A Party 1.1.1. 7 · 6 ··· 2 ·1 = 5040. 1.1.2. Carl: 15· 23 = 120. Diane: 15· 3 · 2 ·1 ...

252 16. Answers to Exercises 1.2.8. {a},{a, c},{a, d},{a, e},{a, c, d},{a, c, e},{a, d, e},{a, c, d, e}. 1.2.9. ZorZ+. The small ...

Answers to Exercises 253 1.5.3. 313. 1.5.4. 6 ·6 = 36. 1.5.5. 1220. 1.5.6. (2^20 )^12. 1.6 Permutations 1.6.1. n!. 1.6.2. (a) ...

254 16. Answers to Exercises 1.8.7. Both sides count the number of ways to divide ana-element set into three sets witha−b,b−c, a ...

Answers to Exercises 255 2.1.10. (Strings) True forn=1.Ifn>1 then to get a string of lengthn we can start with a string of ...

256 16. Answers to Exercises 3 Binomial Coefficients and Pascal’s Triangle 3.1 The Binomial Theorem 3.1.1. (x+y)n+1 =(x+y)n(x+y) ...

Answers to Exercises 257 sincen−n 1 −···−nk− 1 −nk=0. 3.2.2.(a)n! (distribute positions instead of presents). (b)n(n−1)···(n− ...

258 16. Answers to Exercises 3.5.2. (n 0 ) = (n n ) = 1 (e.g., by the general formula for the binomial coeffi- cients). 3.6 Iden ...

Answers to Exercises 259 We can divide the equation by (n k− 1 ) and multiply byk(k+ 1) to get (n−k+ 1)(n−k)−2(n−k+ 1)(k+1)+k( ...

260 16. Answers to Exercises Here the exponent is t^2 m−t+1 − t^2 m+t = (2t−1)t^2 (m−t+ 1)(m+t) . In our case, this is 1900/(41∗ ...

Answers to Exercises 261 1 ;ifnhas remainder 3 when divided by 5 , thenFnhas remainder 2 ;ifn has remainder 4 when divided by ...

262 16. Answers to Exercises 4.2.6. The identity is ( n 0 ) + ( n− 1 1 ) + ( n− 2 2 ) +···+ ( n−k k ) =Fn+1, wherek= n/ 2 . Pro ...

Answers to Exercises 263 4.3 A Formula for the Fibonacci Numbers 4.3.1. True forn=0,1. Letn≥2. Then by the induction hypothesi ...

264 16. Answers to Exercises In the formula of Alice, the rounding plays less and less of a role, so ⌈ en/^2 −^1 ⌉ ∼en/^2 −^1 =( ...

Answers to Exercises 265 on his or her birthday is 1/ 3653 =1/ 48 , 627 ,125. Let’s say there are 2 billion married people; th ...

266 16. Answers to Exercises (indirect assumption)k √ n=a/bthennbk=ak, and so the number of times poccurs in the prime factoriza ...

Answers to Exercises 267 product above has the same remainder when divided bypas the product r 1 r 2 ···rp− 1. But this produc ...

268 16. Answers to Exercises Letpbe any prime number dividingA 0. Thenpmust divide either (C+ B)/2or(C−B)/2. Butpcannot divide b ...

Answers to Exercises 269 6.7.4.(a) Takea= 2 andb= 5. (b) Ifac≡bc(modmc), thenmc|ac−bc, so there is an integerksuch thatac−bc=k ...

270 16. Answers to Exercises add the number of common multiples ofpiandpjfor any two primespi andpj; then we have to subtract th ...