Show that series converges by estimating number of partitions into distinct parts

Question

I need some help with solving the following problem: Let $Q(n)$ be the number of partitions of $n$ into distinct parts. Show that $$\sum_{n=1}^\infty\frac{Q(n)}{2^n}$$ is convergent by estimating $Q(n)$ in some way. I have been trying to do this for a few days now, but without succeeding. Notice that if we only want to show that the series converges and don't care about which method we use, we can do this by considering the infinite product $\prod_{n=1}^\infty\left(1+\frac{1}{2^n}\right)$.

Answer 1

If $a_1 < \dotsb < a_k$ is a distinct partition of $n$ of size $k$, we must have that $a_j \geq j$, and so $$ n = \sum_{j=1}^k a_j \geq \sum_{j=1}^k j \geq \frac{k^2}{2}. $$

Thus, any ordered partition of $n$ must have $k \leq \sqrt{2n}$, and so we have that \begin{align*} Q(n) &= \#\{\text{distinct partitions of }n\} \\ &\leq \#\{\text{partitions of $n$ of size at most $\sqrt{2n}$}\} \\ &\leq \#\{\text{ordered partitions of $n$ of size at most $\sqrt{2n}$}\}. \end{align*}

But the number of ordered partitions of $n$ of size at most $k$ is $\binom{n+k-1}{k-1}$ by the standard stars-and-bars argument, so that we have \begin{align*} Q(n) &\leq \binom{n + \lfloor\sqrt{2n}\rfloor - 1}{\lfloor\sqrt{2n}\rfloor - 1} \\ &\leq (n + \sqrt{2n}- 1)^{\sqrt{2n}- 1} \\ &\leq \exp\{\sqrt{2n}\log(n + \sqrt{2n})\} \\ &\lesssim \exp\Bigl\{n \log\frac{3}{2}\Bigr\}. \end{align*}

Therefore, for large enough $n$, we have that $Q(n)/2^n \leq (3/4)^n$, which is summable.

Answer 2

Let $p(n)$ be the unrestricted partition function. Then we have $Q(n)\le p(n)$. Note that for $|z|<1$

$$ 1+\sum_{n\ge1}p(n)z^n=\prod_{k\ge1}(1-z^k)^{-1}, $$

so we have

$$ \sum_{n\ge1}{Q(n)\over2^n}\le1+\sum_{n\ge1}p(n)\left(\frac12\right)^n=\prod_{k\ge1}\left(1-{1\over2^k}\right)^{-1}<\infty. $$