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:
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).