Question

Let $H_k\left(n\right)$be the number of vectors $x_1,...,x_k$for which each $x_i$is a positive integer satisfying $1\le x_i\le n$and $x_1\le x_2\le ,\dots ,\le x_k.$

(a)Without any computations, argue that

localid="1648218400232" $$\begin{gathered} H_1\left(n\right)=n \\ {H}_k\left(n\right)=\sum _{j=1}^n{H}_{k-1}\left(j\right)k>1 \end{gathered}$$

Hint: How many vectors are there in which $x_k=j$?

(b) Use the preceding recursion to compute $H_3\left(5\right)$.

Hint: First compute $H_2\left(n\right)forn=1,2,3,4,5$.

Short answer

(a) It is proved that

$$\begin{gathered} H_1\left(n\right)=n \\ {H}_k\left(n\right)=\sum _{j=1}^n{H}_{k-1}\left(j\right)k>1 \end{gathered}$$.

(b) The value of$H_3\left(5\right)=35$.

Step-by-step solution

Part (a) Step 1. Prove that H1(n)=n

We have to prove that

$H_1\left(n\right)=n$

$H_1\left(n\right)=n$refers to the ways in which one number $x_i$is selected from $n$positive integers $1$through $n$.

We know that, $1$number can be selected from$n$different numbers in$n$ways.

Therefore,role="math" localid="1648218917857" $H_1\left(n\right)=n$.

Part (a) Step 2. Prove that Hk(n)=∑j=1nHk-1(j)     k>1.

We have to prove that $H_k\left(n\right)=\sum _{j=1}^n{H}_{k-1}\left(j\right)k>1$

For k=1, we have proved that $H_1\left(n\right)=n$.

if k=2.

$H_2\left(n\right)$is the no. of ways of selecting any two positive numbers from 1 through n, as we know this can happen in two ways:

That is we have two numbers $\left(x_1,x_2\right)$from $2$numbers.

Here, $x_2$is the maximum number. $x_2$is either $1\text{or}2$as there are only two members.

For $x_2=1$, we need to select one number from $(2-1)$numbers from $1$through $1$, we denote it as $H_1\left(1\right)$.

For $x_2=2$, we need to select one number from $(2-1)$numbers from $1$through $2$, we denote it as $H_1\left(2\right)$.

So, for n = 2, $H_2\left(2\right)=H_1\left(1\right)+H_1\left(2\right)$

Therefore, $H_2\left(n\right)=\sum _{j=1}^n{H}_{2-1}\left(j\right);k>1$

So, for $H_k\left(n\right)=H_{k-1}\left(1\right)+H_{k-1}\left(1\right)+........+H_{k-1}\left(n\right)$

Hence it is proved that localid="1648220403818" $H_k\left(n\right)=\sum _{j=1}^n{H}_{k-1}\left(j\right)k>1$

Part (b) Step 1. Find the value of H3(5).

We have, $H_k\left(n\right)=\sum _{j=1}^n{H}_{k-1}\left(j\right)k>1$

So,$H_3\left(5\right)=\sum _{j=1}^5{H}_{3-1}\left(j\right)k>1$$H_3\left(5\right)=\sum _{j=1}^5{H}_{2-1}\left(j\right)k>1$

localid="1648229266636" $H_3\left(5\right)=H_2\left(1\right)+H_2\left(2\right)+H_2\left(3\right)+H_2\left(4\right)+H_2\left(5\right)$

$H_2\left(1\right)=H_2\left(1\right)=1$

$H_2\left(2\right)=H_2\left(1\right)+H_2\left(1\right)=1+2=3$

localid="1648220276713" $H_2\left(3\right)=H_2\left(1\right)+H_2\left(2\right)+H_2\left(3\right)=1+2+3=6$

$$\begin{gathered} H_2\left(4\right)=H_2\left(1\right)+H_2\left(2\right)+H_2\left(3\right)+H_2\left(4\right)=1+2+3+4=10 \\ {H}_2\left(5\right)=H_2\left(1\right)+H_2\left(2\right)+H_2\left(3\right)+H_2\left(4\right)+H_2\left(5\right)=1+2+3+4+5=15 \end{gathered}$$

Therefore,$H_3\left(5\right)=1+3+6+10+15=35$