Textbook link: http://discrete.openmathbooks.org/dmoi3/sec_recurrence.html

Problem 2. Think back to the magical candy machine at your neighborhood grocery store. Suppose that the first time a quarter is put into the machine 1 Skittle comes out. The second time, 4 Skittles, the third time 16 Skittles, the fourth time 64 Skittles, etc.

a. Find both a recursive and closed formula for how many Skittles the n^th customer gets, denote it (a_n)_n1

b. Check your solution for the closed formula by solving the recurrence relation using the Characteristic Root technique.

c. Now, consider a recurrence relation b_n= b_n-1 + b_n-2+ b_n-3 + b_n-4: with initial values as above, i.e., b₁= 1, b₂= 4, b₃ = 16 and b₄= 64. Compute b₅

d. Explain why are (a_n)_n1 and (b_n)_n1 distinct sequences.