Deriving a linear recurrence equation from a word problem

[Imagine]

What I'm having trouble with understanding is finding a recurrence relation from a word problem. I've looked at my notes, but I can't make heads or tails of how my professor and TA got from 1 step to another. I've drawn out a tree of the relationship, but I just don't know where do I go from there?

So take problem 1b for example. What should I be looking out for and how do I approach the problem? I've plotted out terms 0 to 3:

Spoiler

and got 1, 3, 7, 15. I then expressed the groups of 3 I made for n =3 in terms of a previous term (i.e group of 3 under AA is Tn-3, AC is Tn-2, etc, etc), and then summed those up to get the recurrence equation of: Tn = 6Tn-3 + 3Tn-2. And then I'm lost after this. Is what I'm doing even right?

EDIT: I took another swing at it, got: Tn = 2Tn-3 + 2Tn-2 + Tn-1. Brute forced all possible combinations for T4, got 35 terms. My recurrence relation also got me 35. Still kind of lost on why my thought process worked out (break tree diagram of recurrence into groups => get a recurrence equation for each of the groups => adding those recurrences up).

[shouri]

Yeah that last line is exactly how you're supposed to go about this. You break it up into groups based on what you would be allowed to add in and into how many places.