【正文】 e enough, it39。s true (by induction onm) that ,A(2m + l) = 2m Next, let39。s use recurrence () and solution ()in reverse, by starting with a simple function f(n)and seeing if there are any constants(α, β, γ) that will dene it. Plugging the constant functionf(n) =1into () says that A neat idea!1 = α。2 = 2 1 + β。3 = 2 1 + γ。hence the values(α, β, γ) = (1, ?1, ?1) satisfying these equations will yield A(n) ? B(n) ? C(n) =f(n) = 1。 Similarly, we can plug in f(n) =n:1 = α。2n = 2 n + β。2n + 1 = 2 n + γ。These equations hold for allnwhenα = 1，β = 2 and γ = 1, so we don39。tneed to prove by induction that these parameters will yieldf(n) = n. Wealreadyknow thatf(n) =nwill be the solution in such a case, because therecurrence () uniquely denesf(n) for every value of n.And now we39。re essentially done! We have shown that the functionsA(n),B(n), and C(n) of (), which solve () in general, satisfy the equationsA(n) = 2m, or n = 2m + l and 0 ≤ l 2m。A(n) ? B(n) ? C(n) = 1。A(n) + C(n) = n.Our conjectures in () follow immediately, since we can solve these equations to get C(n) = n ? A(n) = l and B(n) = A(n) ? 1 ? C(n) = 2m ? 1 ? l。This approach illustrates a surprisingly usefulrepertoire methodfor solving recurrences. First we nd settings of general parameters for which we know the solution。 this gives us a repertoire of special cases that we can we obtain the general case by bining the special cases. We need as many independent special solutions as there are independent parameters (in this case three, for α，β and γ) Exercises 16 and 20 provide further examples of the repertoire approach.We know that the originalJrecurrence has a magical solution, in binary: J (bmbm?1...b1b0)2 = (bm?1...b1b0bm)2, when bm = 1.Does the generalized Josephus recurrence admit of such magic?Sure, why not? We can rewrite the generalized recurrence () asf(1) = α。f(2n + j) = 2f(n) + βj, for j = 0, 1and n ≥ 1, （8）if we let β0 = β and β1 = γ。And this recurrence unfolds, binarywise:f (bmbm?1...b1b0)2 = 2f (bmbm?1...b1)2 + βb0 = 4f (bmbm?1...b2)2 + 2βb1 + βb1 = 2mf (bm)2 + 2m?1βbm?1 + . .+ βb0 = 2mα + 2m?1βbm?1 + . . + βb0.Suppose we now relax the radix2notation to allow arbitrary digits instead of just0and1. The derivation above tells us thatf (bmbm?1...b1b0)2 = (αβbm?1βbm?2 . . . βb1 + βb0)2. （9）Nice. We would have seen this pattern earlier if we had written () in another way:For example, when n = 100 = (1100100)2 our original Josephus valuesα = 1，β = ?1，and γ = 1 yieldas before. The cyclicshift property follows because each block of binary digits(10...000)2 in the representation of nis transformed into(1 ?1... ?1 ?1)2 = (0 0 ... 0 1)2.So our change of notation has given us the pact solution () to the general recurrence (). If we39。re really uninhibited we can now generalize even more. The recurrencef(j) = aj, for 1 ≤ j d。 f(dn + j) = cf(n) + βj for 0 ≤ j d and n ≥ 1, （10）is the same as the previous one except that we start with numbers in radix d and produce values in radixc. That is, it has the radixchanging solution f (bmbm?1...b1b0)d = (αbmβbm?1βbm?2 . . . βb1βb0)c. （11）For example, suppose that by some stroke of luck we39。re given the recurrencef(1) = 34f(2) = 5,f(3n) = 10f(n) + 76 for n ≥ 1f(3n + 1) = 10f(n) ? 2 for n ≥ 1f(3n + 2) = 10f(n) + 8, for n ≥ 1and suppose we want to putef(19). Here we have d=3andc=10. Now 19= (201)3and the radixchanging solution tells us to perform a digitbydigit replacement from radix3to radix10. So the leading 2bees a5, and the 0and1bee76and2, givingf(19) = f (201)3 = (576 ?2)10 = 1258,which is our answer.Thus Josephus and the Jewish{Roman war have led us to some interestinggeneral recurrences.,