If a recurrence has the solution an=c1(2n)+c2(2n)a_n = c_1(2^n) + c_2(2^n)an=c1(2n)+c2(2n), this implies:
The roots are distinct
The roots are repeated
The relation is non-homogeneous
The solution is invalid