Recurrence Relation Poker Chips

Question

enter image description here

I am assuming that the recurrence relation for a) would be $a_n = a_{n-1} + a_{n-2}+ a_{n-3}$. Correct me if I'm wrong. And I have no idea to what the answer for B is. I would really appreciate it if you provide a detailed explanation on how this problem is solved.

Thanks a lot, really.

score 1 · Answer 1 · answered May 10 '14 at 03:25

1

For a, given a stack of height $n-1$, you can put either of two colors on top. For b, a stack of height $n$ can either be a stack of height $n-1$ that you put a blue chip on, or a stack of height $n-2$ that got a blue chip and now you put a red or white on. Can you make recurrences out of that?

answered May 10 '14 at 03:25

Ross Millikan

374,822

No I cannot lol – Roy Kesserwani May 10 '14 at 03:28
If $a_{n-1}$ is the number of legal stacks of height $n-1$, and you can put two kinds of chips on top of each one, what is $a_n$? – Ross Millikan May 10 '14 at 03:41
why is it that if the height n-1, you can put to colors on top. What happened to the third color. – Roy Kesserwani May 10 '14 at 03:54
You can't put whatever color isn't on top now. That would make two in a row. – Ross Millikan May 10 '14 at 04:52
So wouldn't that make my answer right? – Roy Kesserwani May 10 '14 at 05:53
No. We have $a_1=3$ because you can have any single chip. Then $a_2=6$ because we can put two colors on top of any single chip stack. Similarly, $a_3=12, a_4=24, a_n=2a_{n-1}=3\cdot 2^{n-1}$ Your formula would give $a_4=21$ – Ross Millikan May 10 '14 at 23:12

Recurrence Relation Poker Chips

1 Answers1