Hints for the last chapter 9 assignment

s_n = 7 s_n-1 - 12 s_n-2+6
and s₀ = 1 and s₁ = 2.

s_n = 4ⁿ - 3ⁿ + 1

Check that the formula gives you the correct answers for s₀ and s₁

Induction hypothesis:
Suppose that s_j = 4^j - 3^j + 1 for all 0 ≤ j ≤ k where k ≥ 1

s_k = 4^k - 3^k + 1
s_k-1 = 4^k-1 - 3^k-1 + 1

s_k+1 = 7 s_k - 12 s_k-1+6

s_k+1 = 7 (4^k - 3^k + 1)s - 12 (4^k-1 - 3^k-1 + 1)+6

4^k+1 - 3^k+1 + 1

s_n = 1 s_n-1 + 2 s_n-2

xⁿ = x^n-1 + 2 x^n-2

xⁿ = x^n-1 + 2 x^n-2
Collect all terms on one side of the equation: xⁿ - x^n-1 - 2 x^n-2 = 0
Divide the polynomial by x^n-2 (or factor out x^n-2) to get a quadratic equation: x² - x - 2 = 0
Solve by factoring or using the quadratic formula: (x - 2) (x + 1) = 0
x = 2; x = -1

a_n = 2ⁿ and b_n = (-1)ⁿ are solutions to the recursion equation.

A linear combination of a_n = 2ⁿ and b_n = (-1)ⁿ is
u a_n + v b_n = u 2ⁿ + v (-1)ⁿ

Plug n = 0 into the linear combination and set it equal to s₀
Do the same for n=1. You get equations:
u 2⁰ + v (-1)⁰ = 9
u 2¹ + v (-1)¹ = 0

u + v = 9
2u - v = 0
u = 3 and v = 6

s_n = 3 * 2ⁿ + 6 * (-1)ⁿ