Recurrence relations

(a) (3 points) Solve the recurrence relation An+1 = An + An-1 for n >= 2, with A1 = 1 and A2 = 3.

(b) (3 points) You are designing the sleeping car of a train; the hall is on one side of the train and the rooms are on the other side. Each room can have either one or two beds. In a room with two beds, the beds can either be side-by-side or one above the other. Write down a recurrence relation for the number of possible arrangements for the sequence of rooms, if there are n total beds. Explain your logic.

4. Reeurrence relations ta} [3 points] Solve the recurrence relation An+1 = An + A314 for n It: 2. with A1 = 1 and A2 = 3. {b} [3 points} You are designing the sleeping car of a train; the hall is on one side of the train and the rooms are on the other side. Each room can have either one or two beds. In a room with two beds. the beds can either be sidebyside or one above the other. Write down a recurrence relation for the number of possible arrangements for the sequence of rooms. if there are as. total beds. Explain your logic