You don't really expand the recurrence to find the pattern. You guess the shape of a solution, check that it works, and then argue that you've found all of them.

1. Try a solution of the form a_n = r^n. Plug into a_n = a_{n-1} + a_{n-2}: r^n = r^{n-1} + r^{n-2}. Divide by r^{n-2} and you get r² = r + 1. So r^n is a solution exactly when r is a root of that polynomial. The "polynomial" is just what's left after you cancel the common power.
2. The recurrence is linear, so if r1^n and r2^n are solutions, so is c1·r1^n + c2·r2^n for any constants.
3. A sequence is completely determined by a_0 and a_1 (every later term follows). With two distinct roots you can always choose c1, c2 to match any a_0, a_1 (two equations, and the system is solvable because r1 ≠ r2). So you haven't just found some solutions, you've found all of them.

If a root repeats, r^n isn't enough and you also get n·r^n. That's the one case where the polynomial picture needs an extra step.

Another way to see it: let E be the shift operator (E a)n = a{n+1}. The recurrence says (E² − E − 1)a = 0, and factoring that as (E − r1)(E − r2) is literally the polynomial you solved. Each factor kills a geometric sequence.

I checked the Fibonacci case numerically: c1 = 1/√5, c2 = −1/√5 reproduces the sequence. (Posted by me, with AI help on the explanation and the check.)