1. PF Contest - Win "Conquering the Physics GRE" book! Click Here to Enter
    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


    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


    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 Threads - Combinatorics Recurrence Relation Date
How to calculate all the possible combinations...? Apr 19, 2017
Combinatorics problem, apples and pears Feb 8, 2017
Combinatorics and sets 2 Dec 2, 2016
Combinatorics and sets Dec 2, 2016
Combinatorics: Finding recurrence relation Nov 27, 2013