Question

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 a1 , a2 , ..., ak , where a1 = 1, ak = n, and aⱼ < aⱼ ₊ ₁ for j = 1, 2, . . . , k − 1.

Answer 1

`S(k)=2^((k-2))`

Explanation:

`S(k)=S(1)+S(2)+S(3).........S(k-1)\\where\\S(1)=1\\So\\S(k)=2^((k-2))`

where k>1 and S(1)=1