1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Find a recurrence relation.

  1. Apr 9, 2013 #1
    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.

    Thanks in advance for your help
  2. jcsd
  3. Apr 9, 2013 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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?
  4. Apr 9, 2013 #3
    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
  5. Apr 9, 2013 #4


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    No, that's not what I meant by a mapping. I mean a natural way of matching up new sequences with old ones.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted