Every Appliance must have a License and every License must have an Appliance.
But, depending on your needs, a 500 appliance may be able to handle 1000 users. I ran 12k users on a single 5k appliance at one point on a demo license without issue.
So, it really depends on your WAN architecture and the complexity of your policies (If the ClearPass at another site can act as backup for the local site.) Your cheapest build would probably be 2 5k's and 2 500's.
But I don't represent Aruba in any way and couldn't tell you what support would say if you had problems.