Let $H_k(n)$ be the number of vectors $x_1,\dots,x_k$ for which each $x_i$ is a positive integer satisfying $1\leq x_i\leq n$ and $x_1\leq x_2 \leq \dots \leq x_k$.
Without any computations, argue that \begin{equation*} \begin{aligned} H_1(n) & = n & \\ \\ H_k(n) & = \sum\limits_{j=1}^n H_{k-1}(j) & k>1 \end{aligned} \end{equation*}
Let $(x_1,\dots,x_k)$ be a vector such that $x_i\geq 0$ and $x_i\in \mathbb{Z}$ and $1\leq x_i\leq n$.
When $k=1$, then the vector is of length 1. Since $x_1$ is an integer between (and including) 1 and $n$, there are $n$ different choices of integers. Hence $H_1(n)=n$.
When $k=2$, then the vector is of length 2. Since $x_1$ is an integer between (and including) 1 and $n$, we have $n$ options. Now for $x_2$. We know $x_1\leq x_2$. This implies whatever $x_1$ equals $x_2$ has $n-x_1+1$ options (because $x_1$ can be the same as $x_2$). Hence $H_2(n)=n(n+x_1+1)$
Question 1: I know there is a gap in my reasoning because if you try computing $H_2(n)$ with the formulas above, you get $H_2(n)=n(n+1)/2$. Can someone enlighten me on where my thinking is wrong?
Question 2: Am I suppose to use counting arguments for both sides of $H_2(n)=\sum\limits_{j=1}^n H_1(j)$ to show equally?
I am guessing yes.
- Question 3: How am I suppose to extend this argument for the case of generic $k$?
To prove the recurrence, condition on the value $j\in\{1,\dots,n\}$ of $x_k$. Explicitly, if $x_k = j$, we want to count the number of positive integer solutions to $x_1 \le \dots \le x_{k-1} \le j$, which is exactly the definition of $H_{k-1}(j)$.