- #1
AUCTA
- 10
- 0
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