Q. 1.15 - A First Course in Probability

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 

$$\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) for n = 1, 2, 3, 4, 5$.

Step-by-Step Solution

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$.

Part (a) Step 1. Prove that H 1 ( 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,  $H_1\left(n\right)=n$.

Part (a) Step 2. Prove that H k ( n ) = ∑ j = 1 n H k - 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 $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 H 3 ( 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$

$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$

$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$