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

1. Apr 23, 2012

### praecox

1. The problem statement, all variables and given/known data
Find a recurrence relation for Tn, 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.]

2. Relevant equations

(if I had one, this would be easier)

3. The attempt at a solution
So I tried at first to just map out some of the smaller n's:
T0=0
T1=0
T2=1
T3=1
T4=2 (2+2) & (2'+2)
T5=2 (as above)

A nice pattern seemed to emerge for a moment, but then it fell apart:
T6 had (2+2'+2'') and it's permutations (3!=6) and (3+3') and it's 2 permutations. So T6=8.
But T7 only has (2+2'+3) and it's 6 permutations, so T7=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:

T0=0
T1=0
T2=1
T3=1
T4=1 (2+2)
T5=2 (as above)
etc...

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

Last edited: Apr 23, 2012