Kenneth Rosen Edition 7 Exercise 8.1 Question 6 (Page No. 510)

Question

• A. Find a recurrence relation for the number of strictly increasing sequences of positive integers that have 1 as their first term and n as their last term, where n is a positive integer. That is, sequences $a_{1}, a_{2},\dots,a_{k},$ where $a_{1} = 1, a_{k} = n,$ and $a_{j} < a_{j+1} \:\text{for}\: j = 1, 2,\dots,k − 1.$ 
• B. What are the initial conditions?
• C. How many sequences of the type described in $(A)$ are there when $n$ is an integer with $n \geq 2?$