Question

Discrete Mathematics

7. (15 points) Let an be the number of length n ({ne Zin 20}) ternary strings (strings made up of {0, 1, 2), ex. 01211120002) that contain two consecutive digits that are the same. For example, a = 3 since the only ternary strings of length 2 with matching consecutive digits are 00, 11, and 22. Also, a, = 0, since in order to have consecutive matching digits, a string must be of length at least two. a. (10 points) Find a recurrence formula for an b. (5 points) Using recurrence relation found in problem a, write a recursive function code that returns ar when its input is n. (C. Python, or pseudocode is also fine.)

Answer 1

Answer: page- have consecutive digits Note that 90=0 Now consider an The first (n-1) numbers can that are same 091 can not (a) have so So, if it has then we can Let the Last number to be any thing so, then it is 3an- If it does not have, then the last digit is fixed to be the same as the (n-13th digit. so, (1-an-) Thus an = 39n-, + (1-an-1) + qant With a=0 (b) Python code: def num (int n) : if n=:0: retuin o else Me tuon 2 num (n-1)+) R = int(input ("Entesi")) porint (num(R))