I agree with @BalmungSan: The Aux pattern is the best way to support this currently, unless one wants to parameterize everything.
The problem in the original code arises since
Combine[A, A](n, n): Combine[A, A]
That is, the information about what the argument to the constructor was gets lost. The Aux construction preserves that knowledge.
It would be interesting to see what’s the best way to refine Scala’s typing rules to preserve the lost knowledge directly, without having to go through the Aux pattern.