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!

Combinatorics - Recurrence Relation Question

  1. Mar 2, 2012 #1
    1. The problem statement, all variables and given/known data

    For n ≥ 1, let g(n) be the number of ways to write n as the sum of
    the integers in a sequence of any length, where each integer in the sequence is at least 2.

    For n≥3, show that g(n) = g(n-1) + g(n-2).


    2. The attempt at a solution

    I've gone through values of g(n) for small values of 'n,' and it's clear to me that the recurrence relation is the same as that of the Fibonacci, with different starting values of 'n.' However, to prove the relation, I'm trying to split an arbitrary g(n) into two disjoint cases. I feel like somehow I must show that g(n) can be manipulated into two different contexts, one which is the exact same as g(n-1), and another the same as g(n-2). Any ideas? I can't think of how to split this into two cases.
     
  2. jcsd
  3. Mar 2, 2012 #2

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Given a summation of integers that sums to n, there are two possibilities: the summation contains a 2 or it doesn't contain a 2.
     
  4. Mar 2, 2012 #3
    That makes sense. Looking at the possibilities of sequences written out, there seems to be a one-to-one correspondence between sequences in g(n) which contain a 2 and g(n-1), and a correspondence between those which don't contain a 2 and g(n-2). However, I don't see how to map them to each other?
     
  5. Mar 2, 2012 #4
    Actually, scratch that: I might have figured it out.

    For those sequences in g(n-1), do you add 1 to the last number in each sequence? That would give you a sequence which sums to n.

    For those sequences in g(n-2), you append a 2 to the sequence?
     
  6. Mar 2, 2012 #5

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    That looks correct to me
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Combinatorics - Recurrence Relation Question
  1. Combinatorics Question (Replies: 2)

  2. Combinatorics Question (Replies: 4)

  3. Combinatorics question (Replies: 2)

Loading...