a(n+1) = 2^(2*n - 1) + (-1)^n * a(n), so a(n) = 2^(2*n - 3) - (-1)^n * a(n-1). Assume a(n) = 15*a(n-2) + 16*a(n-4) for n > 4. # Plug the original function into the new function. a(n) = 15*(2^(2*n - 7) - (-1)^n * a(n-3)) + 16*(2^(2*n - 11) - (-1)^n * a(n-5)) # Expand. a(n) = 15*2^(2*n)/2^7 - 15*(-1)^n * a(n-3) + 16*2^(2*n)/2^11 - 16*(-1)^n * a(n-5) # Combine like terms. a(n) = 2^(2*n)*(15/2^7 + 16/2^11) - (-1)^n * (15*a(n-3) + 16*a(n-5)) # Simplify. a(n) = 2^(2*n)/2^3 - (-1)^n * (15*a(n-3) + 16*a(n-5)) # Simplify. a(n) = 2^(2*n - 3) - (-1)^n * (15*a(n-3) + 16*a(n-5)) # 15*a(n-3) + 16*a(n-5) is a variation of the formula above, so it can be replaced with a(n-1). a(n) = 2^(2*n - 3) - (-1)^n * a(n-1) # Original function emerges. This shows that the recurrence relation, a(n) = 15*a(n-2) + 16*a(n-4), fits within the original formula. Since a(n) = 15*a(n-2) + 16*a(n-4), a(n) - 15*a(n-2) - 16*a(n-4) = 0. We can use this fact to find the generating function. Assume A(x) is the generating function for a(n). A(x) = x + x^2 + 9*x^3 + 23*x^4 + 151*x^5 + 361*x^6 + 2409*x^7 + 5783*x^8 + 38551*x^9 + 92521*x^10 + 616809*x^11 + 1480343*x^12 + 9868951*x^13 + O(x^14) -15*x^2*A(x) = - 15*x^3 - 15*x^4 - 135*x^5 - 345*x^6 - 2265*x^7 - 5415*x^8 - 36135*x^9 - 86745*x^10 - 578265*x^11 - 1387815*x^12 - 9252135*x^13 + O(x^14) -16*x^4*A(x) = - 16*x^5 - 16*x^6 - 144*x^7 - 368*x^8 - 2416*x^9 - 5776*x^10 - 38544*x^11 - 92528*x^12 - 616816*x^13 + O(x^14) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- (1 - 15*x^2 - 16*x^4)*A(x) = x + x^2 - 6*x^3 + 8*x^4 + 0*x^5 + 0*x^6 + 0*x^7 + 0*x^8 + 0*x^9 + 0*x^10 + 0*x^11 + 0*x^12 + 0*x^13 + O(x^14) # Since a(n) - 15*a(n-2) - 16*a(n-4) = 0, the coefficients of x^n, for n > 4, will cancel out to zero. (1 - 15*x^2 - 16*x^4)*A(x) = x + x^2 - 6*x^3 + 8*x^4 # Divide both sides by (1 - 15*x^2 - 16*x^4). A(x) = (x + x^2 - 6*x^3 + 8*x^4)/(1 - 15*x^2 - 16*x^4) # Factor. A(x) = x*(1 + x - 6*x^2 + 8*x^3)/((1 - 4*x)*(1 + 4*x)*(1 + x^2)) This shows that the generating function of a(n) is x*(1 + x - 6*x^2 + 8*x^3)/((1 - 4*x)*(1 + 4*x)*(1 + x^2)).