How do I prove the integer partition problem in combinatorial mathematics?

Question

Question: Show that the number of partitions of $n$ into $k$th powers $(k>1)$ in which no part appears more than $k-1$ times is always equal to 1.

This is actually an exercise from the book Integer Partition by George E. Andrews and Kimmo Eriksson.

Here are some of my ideas for proof. if $k \ge n$, the partition that satisfies the problem can only consist of 1. But if $k<n$, I think the existence of partition can be proved by a process similar to obtaining binary, but I have no idea how to prove the uniqueness of partition.

Answer 1

The question as stated is wrong. Take $k=2$, we are looking for partitions of $n$ into sums of distinct squares. Such partitions do not always exist (for $n=2$, $n=3$, $n=6$ for instance) and when they do exist there are at least two of them (one may or may not include $0^2=0$ among the squares), and there may be more even when excluding $0^2$, for instance $65$ can be partitioned as $64+1$ or as $49+16$.

So what you probably meant to ask is partitions of $n$ into powers of $k$ instead, which is something entirely different. Indeed every natural number can be uniquely partitioned into a sum of distinct powers of $2$. Once you see why, you can easily see how to generalise to larger $k$.