Geometric recurrence, prove $g(k)=3g(k-1)-2g(k-2) is g(n)=2^n+1$

Question

Geometric recurrence, prove g_k = 3g_(k-1) - 2g_(k-2) is g_n = 2ⁿ+1 using iteration.

g1 = 3, g2 = 5

So,

g₃ = 3g₍₂₎ - 2g₍₁₎ = 3(5) - 2(3) = 9 <---- *which is 2³+1 = 8+1 = 9

I'm unsure how to prove this?

As k as an exponent not a multiplication?

Answer 1

$g_k - g_{k-1} = 2(g_{k-1} - g_{k-2}) = 2^2(g_{k-2} - g_{k-3}) = 2^{k-2}(g_2 - g_1) = 2^{k-2}(5 - 3) = 2^{k-1}$.

Now let $k$ goes from $1$ to $n$:

$g_2 - g_1 = 2$

$g_3 - g_2 = 4$

....

$g_n - g_{n-1} = 2^{n-1}$.

Add these up telescopingly:

$g_n - g_1 = 2 + 4 + ... + 2^{n-1} = 2^n - 2$.

So: $g_n = 2^n - 2 + g_1 = 2^n - 2 + 3 = 2^n + 1$.