Sum of number of partitons of $k$ into distinct parts as $k$ ranges from $1$ to $n$ is less than $n$th power of $2$.

Question

Prove, with a direct combinatorial argument,that for all positive integers $n$, we have $q(1)+q(2)+...+q(n) \leq 2^{n}$, where $q(n)$ denotes the number of partitons of n into distinct parts.

I have found this problem in the book 'Introduction to Enumerative and Analytic Combinatorics' by Miklos Bona. I am going nowhere with this problem. Can anyone please give me a hint or a solution?

Answer 1

Every partition of a number $k\le n$ into distinct parts corresponds uniquely to a subset of $\{1,2,\dots,n\}$; the inequality follows since the number of such subsets is $2^n$.