A sequence of integers $x_1, x_2, x_3, \dots$ is defined by $x_1 = 3$, $x_2 = 7$ and $$ x_k = 5x_{k-1} - 6x_{k-2}$$ for $k \geq 3$. Prove that $x_n = 2^n + 3^{n-1}$ for all $n$.
I suppose that the way to prove this is by induction. My base case (if $n=1$ , $x_1=3$) is true. My inductive hypothesis would to assume that $x_k=5x_{k-1}-6x_{k-2}$ and $x_k=2^k+3^{k-1}$ is true?
Then I prove for the case of $n=k+1$, so that $x_{k+1}=5x_k-6x_{k-1}$ and $x_{k+1}=2^{k+1}+3^{k}$?
The formula for the sequence $x_k$ is confusing me a lot. I'm pretty sure I have to equate $x_k$ and $x_n$ to prove that $x_n$ (with $n=k+1$) is equal to $x_k$ (with $k=k+1$).
The thing is I can't think of anyway is how to get rid of the subscripted $x$'s in $x_k$ (and $x_{k+1}$). If I substitute those things like $x_{k-1}$ and $x_{k-2}$ from the $x_k$ formula, then in the $x_n$ formula (with $n=k-1,n=k-2$), the numbers gets really messy.
I know that I am misunderstanding a fundamental aspect of this question. I would appreciate any guidance. (No need to actually solve the problem for me or anything - a mindset, or a hint to help me understand or get started would be great.)
$x_1 = 3, x_2=7, x_k = 5x_{k-1} - 6x_{k-2}$. We want to show $x_n = 2^n+3^{n-1}$
Base case, as you said, works (for $n=1$ and $2$). Inductive hypothesis would be, suppose $x_{k}$ and $x_{k-1}$ satisfy the above formula. Then we want to show the formula holds for $x_{k+1}$ $$x_{k+1} = 5(2^{k} + 3^{k-1}) -6(2^{k-1} + 3^{k-2})\\ \implies x_{k+1} = 5(2^{k} + 3^{k-1}) -3\cdot2^{k} - 2\cdot 3^{k-1}\\ \implies x_{k+1} = 2^{k+1} + 3^{k}$$ So $x_{k+1}$ also satisfies the formula and you're done.