The last time I started a business in Washington State, it involved putting the company name and address on a form, attaching a check for $50, and mailing it to the government.
You can start a business in Germany too for 15€ (Gewerbeanmeldung). The more "complicated" stuff (as I founded my UG in Germany it was a few clicks and one personal appointment) is required if you want the limited liablity part. So the trust establishment that it IS a real company behind.
In the UK it's really easy too, perhaps even easier, the registration form is entirely online [0] and then you pay £12.