A lower bound for Waring's Problem for sufficiently large numbers: $G(k) \ge k+1$

I need to show that, if $G(k)$ is the solution to Waring's Problem for $k$ and for sufficiently large $n$, then:

$$G(k) \ge k + 1$$

So I need to establish that:

$$x_1^k + x_2^k + \dots + x_k^k = n \tag{1}$$

fails for an arbitrary number of values. I've a few solutions to this, but they seem outside the scope of the course (4th year Ele.Num.Theory).

A hint is that we should use an earlier result that the number of solutions to:

$$x_1 + x_2 + \dots + x_k \le n$$ is $$\binom{n + k}{n}$$

I don't see how I can establish the result given this information. Maybe there's a better way?

• thank you for the edits monhawk. I'm still getting used to Latex – user45793 Oct 24 '12 at 10:10
• What I have so far is that there are $n^{\frac{1}{k}} + 1$ values for $x_i$ that could possibly satisfy $(1)$. Hence, choosing $k$ of them where repetitions are allowed and order is unimportant is: $$\binom{n^{1/k} + k + 1}{n^{1/k} + 1}$$ which is greater than the number of solutions to: $$x_1^k + x_2^k + \dots + x_k^k \le n$$ which is in turn greater than the number of solutions to $(1)$. Than just need to show this last binomial coefficient grows at a rate less than $1$ for large $n$? Can someone confirm I'm on the right track with this? – user45793 Oct 24 '12 at 16:33

Hint 1: You use the result to count the number of different ways to choose $k$ things from a pool of $m$ where order is unimportant but repetitions are allowed.
Hint 2: What is the largest that $x_i$ could possibly be?
Hint 3: How many solutions are there to $x_1^k + \cdots + x_k^k \color{blue}\le n$?
• Thanks for the reply! Doesn't the first result count the number of ways to partition n into k+1 partitions? And ya, $x_i \le n^{1/k}$ – user45793 Oct 24 '12 at 8:28
• @Carl Yes. Note that there is a correspondence between $k+1$ numbers summing to exactly $n$ and an inventory of $n$ things chosen from a pool of $k+1$. – Erick Wong Oct 24 '12 at 8:33
• @Carl Yes. You just need to show that $\binom{n^{1/k} + k + 1}{n^{1/k} + 1} < n$ for large enough $n$. Then there are fewer sums than there are values between 1 and $n$ (technically you should show that the difference between the LHS and RHS is arbitrarily large). – Erick Wong Oct 24 '12 at 16:41