518 ANSWERS TO EXERCISES
and this is the case x = N of exercise 22. 5.55 Let Q(k) = (k+Al)...(k+AM)Zand
Then t(k+ 1)/t(k) = P(k)Q(kis a nonzero polynomial.
R(k) = (k+Bl)...(k+BN). l)/P(k- l)R(k), where P(k) = Q(k) -R(k)
5.56 The solution to -(k+l)(k+2) = s(k+l)+s(k) is s(k) = -ik2-k-a; hence t (~:) 6k= i(-l)kp’(2k2 +4k+ 1) + C. Also
(-l)k-’ =- k-t 1 - ‘+‘r”*> (,+,- ‘-)*) 4
2
= v(2k2+4k+1)+; 5.57 We have t&+1)/t(k) = (k-n)(k+l +B)(-z)/(k+l)(k+O). Therefore we let p(k) = k+ 8, q(k) = (k- n)(-z), r(k) = k. The secret function s(k) must be a constant 0~0, and we have k+B
= (-z(k-n)--k)as;
hence 010 = -l/(1 + z) and 8 = -nz/(l + z). The sum is
t (;)zk(“-+6k = -&(;~;)z’+c (The special case z = 1 was mentioned in (5.18); the general case is equivalent to (5.1311.) 5.58
If m > 0 we can replace (:) by $, (;I\) and derive the formula T,,, =
$T,,-I,~-~ - 6 (“i’). The summation factor (t)-’ is therefore appropriate:
We can unfold this to get Tm,n
- = To,n-m - H, + H, - H,-, . Lx
Finally To,~ ,,, = H,. ,,,, so T,,,, = (z) (H, -H,). (It’s also possible to derive this result by using generating functions; see Example 2 in Section 7.5.) 5 . 5 9 t.)*O,kal (y)[j=Llognrkj] = ti>0,k>, (~)[m’
O (‘j’)(mj+’ - mj) = (m-- l)tjao
which is
