# Homework Help: Find a recurrence relation.

1. Apr 9, 2013

### AUCTA

1. The problem statement, all variables and given/known data
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

2. Relevant equations

Just recurrences

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

2. Apr 9, 2013

### 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?

3. Apr 9, 2013

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

4. Apr 9, 2013

### haruspex

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