Daniel Walker Howe explains that counterinsurgency has been difficult for a long time:
The Seminoles in Florida Territory proved the most difficult of the southeastern tribes to expel. Willing to fight for their homes, they put up a resolute resistance and benefited from a remote defensible bastion and the assistance of runaway slaves. A treaty consenting to Removal, extorted from a group of Seminoles in 1833 when they visited Oklahoma, was repudiated by the tribe but accepted as binding by the administration. In December 1835, a hundred soldiers under Major Francis Dade were annihilated by a combined force of Indians and blacks. When Jackson left office in March 1837, the federal government had undertaken a serious war effort, and the fate of the Seminole tribe was still unresolved. Before it was through, the government would spend ten times as much on subjugating the Seminoles alone as it had estimated Removal of all the tribes would cost.
I always think it’s strange that people have this conception of the United States as a country built on laissez faire somehow. “Send in the army to kill the Indians and take their land” is kind of the ultimate big government program. The land was then sold (often at sub-market rates) and the revenue helped finance both the army and the transportation infrastructure needed to make the whole thing work.