Characteristic polynomial of recursion with exponential term

74 Views Asked by At

I have this recurrence relation as part of a larger problem: $a_k=2a_{k-1}+2^{k-2}.$ With recurrence relations with a constant term we can rearrange things and shift the index, but I'm not sure how to write a closed form for something like this. Wolfram Alpha gave a nice formula, but not explanation of course. I was tempted to assume some polynomial degree but it's exponential, so I'm not sure where to start. How do I write a closed form for this?