Combinatorics - Recurrence Relation Question

[luke8ball]

Homework Statement

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.

 

[Office_Shredder]

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.

 

[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?

 

[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?

 

[Office_Shredder]

That looks correct to me