Exact solution of a minimal recurrence

[[abstract]]In this note we find the exact solution for the minimal recurrence S-n = min(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 inverted 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 interesting combinatorial property. With the exact solution, we can prove an optimal construction of certain fault tolerant circuits. (C) 2000 Elsevier Science B.V. All rights reserved.[[note]]SC