Information olympiad ques

Question

A k-bounded list of length n is a sequence [x1, x2, . . . , xn] where each xj is an integer between 0 and k, inclusive. A good list is one that does not contain three consecutive values 0, 1, 0. For example, for n = 4 and k = 2, [2, 0, 0, 1] and [1, 0, 0, 1] are good lists while [0, 1, 0, 2] and [0, 0, 1, 0] are not. Let good(n, k) be the number of good k-bounded lists of length n. For instance, the good 1-bounded lists of length 2 are {[0, 0], [0, 1], [1, 0], [1, 1]}, so good(2, 1) = 4. Similarly, you can check that good(4, 1) = 12 and good(3, 2) = 26. Your task is to compute good(n, k) for the following values of n and k. (a) good(7, 1) (b) good(7, 3) (c) good(20, 1)