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)).