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!

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

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    No, that's not what I meant by a mapping. I mean a natural way of matching up new sequences with old ones.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Find a recurrence relation.
Loading...