Verify that an=n⋅2na_n = n \cdot 2^nan=n⋅2n is a solution to an=4an−1−4an−2a_n = 4a_{n-1} - 4a_{n-2}an=4an−1−4an−2 by substituting into the recurrence.
LHS =n⋅2n= n \cdot 2^n=n⋅2n, RHS =4(n−1)⋅2n−1−4(n−2)⋅2n−2=n⋅2n= 4(n-1) \cdot 2^{n-1} - 4(n-2) \cdot 2^{n-2} = n \cdot 2^n=4(n−1)⋅2n−1−4(n−2)⋅2n−2=n⋅2n ✓
The recurrence has constant coefficients; n⋅2nn \cdot 2^nn⋅2n cannot be a solution
LHS =n⋅2n= n \cdot 2^n=n⋅2n, RHS =2n⋅2n= 2n \cdot 2^n=2n⋅2n; not equal
LHS =n⋅2n= n \cdot 2^n=n⋅2n, RHS =(n+2)⋅2n= (n+2) \cdot 2^n=(n+2)⋅2n; not equal