I have an induction problem that I have no idea how to start. So the question goes like this.
Let $x_1=1$, $x_2=2$ and $x_n=x_{n-1} + 2x_{n-2}$.
Prove that $x_n=2^{n-1}$ for all $n$ in the natural numbers.
I know the base case is true but after that I do not know what to do. I do not want the answer, but rather a guide on the first few steps. I do not understand induction on sets like this. Thank you for your help.
You can prove it by induction. You checked base cases, so now you should prove induction.
$$ \left(\forall n \in \mathbb{N}\right)\left(\left(x_n = 2^{n-1} \wedge x_{n+1} = 2^{(n+1)-1} \right)\Rightarrow x_{n+2}=2^{(n+2)-1}\right) \Longleftrightarrow \\ \left(\forall n \in \mathbb{N}\right)\left(\underbrace{x_n = 2^{n-1} \wedge x_{n+1} = 2^{n}}_{\mathrm{Assumption}} \Rightarrow \underbrace{x_{n+2}=2^{n+1}}_{\mathrm{Thesis}}\right)$$
From $x_n = x_{n-1}+2 x_{n-2}$ and assumptionis easy to obtain $x_{n+2} = 2^{n+1}$
$$x_{n+2} = x_{n+1} + 2 \cdot x_{n} = 2^{n} + 2^{1} \cdot 2^{{n-1}} = 2^{n} + 2^{n-1+1} = 2 \cdot 2^{n} = 2^{n+1}$$
Which proves the inductive thesis. By virtue of the above steps and mathematical induction...
In fact, it will be more elegant if you prove$\left(x_{n-2} = 2^{n-3} \wedge x_{n-1} = 2^{n-2} \Rightarrow x_{n} = 2^{n-1}\right)$, but I believe you can modify it by your own.