Discrete: Recurrence relation for sum of integer using only 2's and 3's.

[praecox]

Homework Statement

Find a recurrence relation for T_n, the number of ways to write an integer n as the sum of terms, each of which is 2 or 3, and the order matters. [So 2+3 and 3+2 are different sums for 5.]

Homework Equations

(if I had one, this would be easier)

The Attempt at a Solution

So I tried at first to just map out some of the smaller n's:
T₀=0
T₁=0
T₂=1
T₃=1
T₄=2 (2+2) & (2'+2)
T₅=2 (as above)

A nice pattern seemed to emerge for a moment, but then it fell apart:
T₆ had (2+2'+2'') and it's permutations (3!=6) and (3+3') and it's 2 permutations. So T₆=8.
But T₇ only has (2+2'+3) and it's 6 permutations, so T₇=6.

I'm thinking that f(n) is probably dependent on f(n/3) or f(n/2), or both. I don't think it's going to be a simple f(n) based on f(n-1)... but I could be wrong.

It seems like when finding recurrence relations you just have to have an aha! moment - and I'm not having one on this. Any help would be awesome!

FYI: I'm using 2' and 2'' just to keep track of the permutations, since order matters, just to help me remember that (2+2')≠(2'+2).

EDIT: I misunderstood the problem. The permutations of 2's and 3's, like in the above sums of 5, have order matter. But for 2+2+2...+2, order does not matter. So I think I actually have it now:

T₀=0
T₁=0
T₂=1
T₃=1
T₄=1 (2+2)
T₅=2 (as above)
etc...

So for n>3, f(n)=f(n-2)+f(n-3).

 

[mighty2000]

This recurrence relation works because to get to Tn, you can either add a 2 to the previous sum (giving you Tn-2) or add a 3 to the previous sum (giving you Tn-3). This covers all possible ways to get to Tn, and since order matters, you have to consider all possible combinations of adding 2's and 3's.

Hope this helps! Let me know if you have any further questions.