Solving the Subset Problem: Finding the Count of Valid Sets from 1 to N

[haruspex]

Is there a general strategy to finding recurrence relationships? Or is it more of an art than science?

It's a bit of both. Let me summarise the steps I went through.
First, I simplified the problem to one I thought should be easier to handle while still retaining essential features: sum of subset >= max in set (A(N)). If the subset had A(N) you were done; if not, we could represent the target as >= A(N-1)+A(N-3). Or we could think of that as dropping A(N) from the set, so now we had a target of A(M)+A(M-2) out of the set {..., A(M)}, where M = N-1. Again, either we used A(M) or we didn't. Repeating this process produced a set of relationships between different variations of the problem, i.e. different targets based on different combinations of high order elements of the set.
So now I had a set of simultaneous equations, but in which the unknowns were snapshots out of entire sequences (C(n), D(n) etc.). It wasn't hard to get this down to the 2 you saw, C(n) and D(n), and then to find how to map from these to the desired G(n).
Having obtained a recurrence relation of the form:
G(n) = some linear combination of G(n-1)...G(n-k) + f(n)
the next step is to consider just the homogeneous piece, i.e. throw away the f(n).
The reason is that if you have any solution G of the full equation and a solution H of the homogeneous equation then G+H is also a solution of the full equation. So armed with all possible solutions of the homogeneous and one of the inhomogeneous you can get all solutions of the inhomogeneous.
To solve the homogeneous in normal arithmetic just assume G(n) = λⁿ for some unknown constant, λ. This produces a polynomial in λ. The general solution is then a linear combination of these different roots each raised to n. But this wouldn't work mod 1bn - the polynomial had no roots. So I could find nothing better than to represent the relation as a matrix, as ClifD had already done.
But there still remained the inhomogeneous part, f(n), which had the form a.2ⁿ + b. The trick here was to treat the two pieces separately.
For the +b, it looked like it should be linear. So I just wrote down G(n) = c.n, substituted in the full equation and found c.
For the a.2ⁿ, G(n) = m.2ⁿ was the obvious choice.
At this point it looked strange because m was a fraction, but I trusted it would all come out in the wash.
Finally, I needed to kick the H sequence off in such a way that
G(n) = H(n) + c.n + m.2ⁿ
matched the starting values of G. I puzzled over that for a while, but it's trivial! Just set H(n) = G(n) - c.n - m.2ⁿ for n = 1 to 7.

HTH

 

[haruspex]

Obviously his procedure should take only about half as long as mine all else being equal, though of course all is not perfectly equal, but close. His does require adding n + 5/9*(2^n) back on at the end, but still his approach retains a substantial advantage.

The main advantage is that M becomes constant. This allows enormous acceleration. To compute P = M^k only requires log(k) steps instead of k steps.
P = I; // identity matrix
while (k>0) {
if ((k&1) > 0) P *= M;
M *= M;
k >>= 1;
}

 

[ClifDavis]

The main advantage is that M becomes constant. This allows enormous acceleration. To compute P = M^k only requires log(k) steps instead of k steps.
P = I; // identity matrix
while (k>0) {
if ((k&1) > 0) P *= M;
M *= M;
k >>= 1;
}

Yep, though he seemed to be familiar that part of it okay up front and was fine with the idea as applied to A(k).

I appreciate the mini-tutorial on solving homogeneous recurrence relationships by the way. I've probably seen that at one point or another but have long since forgotten. Just remembered that it could be done, not how.

Clif