Exact solution of a minimal recurrence

In this note we find the exact solution for the minimal recurrence S-n = mi n(k=1)([n/2]) {aS(n-k) + bS(k)}, where a and b are positive integers and a greater than or equal to b. We prove that the solution is the same as that of the recurrence relation S-n = aS(inverted right perpendicular n/2 invert ed left perpendicular) + bS ---n/2 ---. In other words, S-n = S-1 + (a + b - 1)S-1 Sigma(i=1)(n-1) a(z(i))b----lg n----z(i), where z(i) is the number of zeros in the binary representaion of i. The proof follows from an intere sting combinatorial property. With the exact solution, we can prove an opti mal construction of certain fault tolerant circuits. (C) 2000 Elsevier Scie nce B.V. All rights reserved.