# Homework Help: Combinatorics - Recurrence Relation Question

1. Mar 2, 2012

### luke8ball

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. Mar 2, 2012

### Office_Shredder

Staff Emeritus
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.

3. Mar 2, 2012

### luke8ball

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?

4. Mar 2, 2012

### luke8ball

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?

5. Mar 2, 2012

### Office_Shredder

Staff Emeritus
That looks correct to me