I was thinking about this more today, and I hope it helps a little. I've been out of the math program for quite some time now. If this question were to allow for any linear combination of (a^n) and (b^m) then the solution would be trivial as 1^n = 1 would be considered a basis for all of n.
The first thing that I did was write down a list of exponent values, in an attempt to see if I could find a "geometry" of differences. However, I realized that if we were to consider your question a variation of having a spanning set of exponential values, then the set of values generated by x^4 is a subset of x^2, since (x^2)^2 and x^2 is a natural number. It follows that we then only have to consider the elements generated by x^p where p is a prime number.
x^2: 4 9 16 25 36 81 100 121 144 169 196 225 256 289 324 361 400 ...
x^3: 8 27 64 125 216 312 ...
x^5: 32, 243, ...
x^7: 128, ...
Now note that: n^2 = (n-1)^2 + (2n+1) and hence the difference of consecutive odd numbers is odd. So by inspection 1=9-8 = 3^2-2^3 and 3=4-1. By Row (i) 5 = 9-4, 7=16-9, 9=25-16, ... and so on. (although there are alternative solutions to your problem, like 7=128-121) Hence we know that all odd numbers have at least one solution.
I'm still working on a generalization for even numbers, if possible, using mainly algebra. I was trying to search for a geometry, but it isn't obvious yet. 2 = 27 - 25, 4 = 36 - 32, 6 = ?, 8 = ?, 10 = ?, 12 = 16 - 4, ...
ex. Remainders of consecutive differences in an exponent row. (using Pascal's triangle for quick expansion of exponential terms) and trying to discern their natures. Recall we only have to work with prime exponents.
n^3 - (n-1)^3 = 3n^2 + 3n + 1 = 3(n^2 + n) + 1
n^5 - (n-1)^5 = 5n^4 - 10n^3 + 10n^2 - 5n + 1 = 5(n^4 -2n^3 + 2n^2 - n) + 1
Remainders of non-consecutive differences in the same row
n^2 - (n-2)^2 = 4n - 4 = 4(n-1)
Remainders of differences of two consecutive bases with the same exponent
a^n - (a-1)^n = a^n [1 - (1 - 1/a)^n