A circular disk is cut into n distinct sectors, each shaped like a piece of pie and all meeting at the centre point of the disk. Each sector is to be painted red, green, yellow, or blue in such a way that no two adjacent sectors are painted the same color. Let Sn be the number of ways to paint the disk.

(i) Find a recurrence relation for Sn.

(ii) Solve the recurrence relation.

(Note: It is a circular disk, so the start sector and the end sector are adjacent.)