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

Question

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?

Answer 1

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$?

Answer 2

I just received an answer for this. It may or may not be what you're looking for: Bounds for Waring's Problem