$4.$ Write and solve a recurrence relation giving the number of strings of

n digits containing at least one $3.$ For example, if n $=5,$ then $02309$

would be one such string.

In particular, let f$($n$)$ be the number of strings of n digits with at

least one $3.$ First, write an equation f$($n$)=,$ where the $***$ part

contains smaller sub$-$problems, i$.$e$.$ the f$($j$)$ terms all have j $<$ n$.$

Then give a base case for the recurrence. Finally, use guess and check

to solve the recurrence to within $\backslash$Theta $()$ bounds. Hint: you may find the

Master method useful for getting a good guess.