Exact Solution of a Minimal Recurrence

Abstract

In this note we find the exact solution for the minimal recurrence Sn = min[2/1]k=1{aSn-k + bSk}, where a and b are positive integers and a ≧ b. We prove that the solution is the same as that of the recurrence relation Sn = aS[n/2]+bS[n/2]. In other words, Sn = S1+(a+b-1)S1Σn-1 i=1 a=(i) b[lg n]-z(i), where z(i) is the number of zeros in the binary representation of i. The proof follows from an interesting combinatorial property.