Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 0 down vote accepted

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

share|cite|improve this answer
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
Am I on the right track? Im still at this – user45793 Oct 24 '12 at 16:00
@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

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.