題組內容

6. Suppose that the balls only come in three colors: red, green and blue. For n≥1 , let  cn count the number of ways a sequence of balls of length n where there are no consecutive green balls and no consecutive blue balls. For example, if n=2, c2= 7, because the sequences can be (red, green), (green, red), (red, blue), (blue, red), (green, blue), (blue, green) and (red, red). (20%)

(a) Show that (you should give a detail explanation) the recurrence relation for is: .