What is the recurrence relation for strictly increasing sequences from 1 to n?

[AUCTA]

Homework Statement

Find a recurrence relation for the number of stricly 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 aj < aj+1 for j = 1, 2, ...k - 1

Homework Equations

Just recurrences

The Attempt at a Solution

An = An-1 + An-2 + An-2 + An-3 + ... + An-k+ 1 since you j can equal 1, 2, 3, ... k - 1 and every step
allows for a recurrence for that given number of steps. I just do not think the solution can be made like that. I thought about something like writing every large jump in terms of single jumps but I am not sure.

Thanks in advance for your help

 

[haruspex]

If n is increased by 1, what sequences are possible that were not possible before? Can you think of a mapping between these and those that were already possible?
What sequences, if any, are no longer possible?

 

[AUCTA]

Any sequence including n + 1 is a new sequence.

For the mapping we can think about it like this :
Total = New + Old
Old = An-1 where n is effectively n + 1

I am not exactly sure on how to compute the number of new possible combinations

 

[haruspex]

Any sequence including n + 1 is a new sequence.

For the mapping we can think about it like this :

No, that's not what I meant by a mapping. I mean a natural way of matching up new sequences with old ones.