There's an assignment which I've been working on so far. Moreover, there are a certain number of questions that I'm stuck at the moment. Could you please help me with these kinds of questions?

. Solve each of the following recurrence relations, with the given initial conditions: {a}nn+1= 2041+ 2\" +3 with on = 4; {b} on+2 = on +41: with on = :11 = 1. . In Xanadu, there are onl)r two sorts of coin: round 2 cent pieces and square 5 cent pieces. Let c.l be the number of ways of making up 11. cents using 2 cult and 5 cent pieces. {For example, cm 2 2, since you could either use two 5 cent pieces or ve 2 cent pieces; while 1:7 2 1 since the only possibility is to use one of each.) {a} Explain clearly why u... = 14..-; + 14..-,5 11\"-? for all n 2 7. {b} What is the least number of initial conditions required to determine all values of an from the recurrence relation? {For example, 1:; = 1 would count as one initial condition.) You are not required to solve the recurrence relation. . Consider instruction table at right, which species a set of eight rE-state This as the 'wildcard' *s take on all possible valid values. {a} Mat is the Beaver number ${M} for this set of Turing machines? (b) Explain how each at aects the number of steps for which the TM runs; and what is its e'ect on the tape. [c] Give the explicit full instruction table for the machine in the set that [i] leaves the minimum number of Is on the tape, and also (ii) halts with the head reading a '1'. . Use Mathematical Induction on n to prove that if the TM '3s' is started 1 with a blank tape, after 1011 + 3 steps the machine will be in state 3 0 ith th t : ...0 I011] \"011100.... w e apereadlng { ]I T ; 0R0 That is, although there are three states with halting instructions, show why 1R4 none of those instructions is actually encountered, and formulate this into 3 DR]- a proof that the machine 3s does not halt when started with a blank tape