|
[ Pobierz całość w formacie PDF ]
.Working modulo 5 we find == 3; hence there are no solutions for 100 104.Similarlythere are none for 120 n 124; we have found all three solutions.(By exercise 6.51(d), we always have andif p is any prime 5.The argument just given shows that these are the only 532 ANSWERS TO EXERCISESsolutions to if and only if there are no solutions to p0 (Attention,(mod p) for 0 p.The latter condition holds not only for p = 5 butHere s an interest-also for p = 13, 17, 23, 41, and 67-perhaps for infinitely many primes.Theing condition tonumerator of H,, is divisible by 3 only when n = 2, 7, and 22; it is divisibletest, for as manyby 7 only when n = 6, 42, 48, 295, 299, 337, 341, 2096, 2390, 14675, 16731,16735, and 102728.)6.53 Summation by parts yields6.54 (a) If m p we have S,(p)(mod p), since 1when1(b) The condition in the implies that the denominator of is notdivisible by any prime p; must be an integer.To prove the hint, we (The numerators ofBernoulli numbersmay assume that n 1.Thenhave importantconnections tothe known resultsabout Fermat sPLast Theorem; seeRibenboimis an integer, by and part (a).So we want to verify that noneof the fractions + 1) = k + 1) has adenominator divisible by p.The denominator of isn t divisible by p,since has no in its denominator (by induction); and the denominatorof k + 1) isn t divisible by p, since 2n k + 1 2will be 6 unless is also prime.In the latter case we can tryuntil we eventually hit a (since n divides 2 + 2 1).,(This proof does not need the more difficult, but true, theorem that there areinfinitely many primes of the form 6k 1.) The denominator of can be 6also when n has values, such as 49. A ANSWERS TO EXERCISES 5336.55 The stated sum is by Vandermonde s convolution.To get differentiate and set x = 0.6.56 First replace by ((k m) + m) n + 1 and expand in powers ofk m; simplifications occur as in the derivation of (6.72).If m n orm 0, the answer is (-1 Otherwise we need to take thelimit of (5.41) minus the term for k = m, as x the answer comes to6.57 First prove by induction that the nth row contains at most threedistinct values A,,if n is even they occur in the cyclic or-der while if n is odd they occur in the cyclic orderAlso=== CB=It follows that A, = (See exercise 5.75 for wraparoundbinomial coefficients of order 3.)6.58 (a) =(b)(These formulas are obtained by squaringor cubing Binet s formula (6.123) and summing on n, then combining termsso that and disappear.) It follows that ,(The corresponding recurrence for mth powers has been found by andMotakin6.59 Let m be fixed.We can prove by induction on n that it is, in fact,possible to find such an x with the additional condition x 2 (mod 4).If xis such a solution, we can move up to a solution modulo because, (mod3".either x or x + or + will do the job6.60 + + 1, 1, and 1 are the only cases.Otherwisethe Lucas numbers of exercise 28 arise in the=== =(We have= in general.)6.61 = ,when m is even and positive.Thesecond sum isfor n 1. 534 ANSWERS TO EXERCISES6.62 (a) A,, = -- and = Incidentally,we also have = and A,, (b) A table ofsmall values reveals thatL n odd.= + 1) because =and = 1).Notice that = even]Similarly, = ++ ) = 2 This quantity can also beexpressed as even] + ) [n odd].6.63 (a) There are with = n and (n with n.(b) Each permutation.of., n- leads to n permutations=.If.has k excedances,there are k+ 1 values of j that yield k excedances in.the remainingn- k values yield k+ 1.the total number of ways to get k excedances6.64 The denominator of is by the proof in exercise 5.72.The denominator of [ is the same, by because = 1 andis even for k > 0.6.65 This is equivalent to saying that is the probability that wehave = k, when , are independent random numbersuniformly distributed between 0 and 1.Let =.) mod Thenare independently and uniformly distributed, and.+is the number of descents in the y s.The permutation of the y s is random,and the probability of k descents is the same as the probability of k ascents.6.66 We have the general formulafor m 0,analogous to (6.38).When m = 2 this equals( ( I ) ) =+6.67 (It wouldbeniceto automate the derivation of formulas such as this.) A ANSWERS TO EXERCISES 5356.68 1 1 + = , and everything converges when
[ Pobierz całość w formacie PDF ]
zanotowane.pldoc.pisz.plpdf.pisz.plhanula1950.keep.pl
|