<s>[INST] Prove By Induction $U_n=2^n+1.$ Given that $U_1=3,U_2=5,$ and $U_{n+2}-3U_{n+1}+2U_n=0.$
Show that $U_n=2^n+1.$ 
I'm stuck at showing that if $P(n+1)$ is true if $P(n)$ is true.
 [/INST] Consider that it is true for $n=1$ and $n=2$:
$n=1\implies U_n=2^1+1=3$
$n=2\implies U_n=2^2+1=5$.
Now, assume that it is true for $n=k$ and $n=k+1$. We prove that it is true for $n=k+2$.
Substitute $n=k$ (this is different from the previous $n$) into the equation $U_{n+2}-3U_{n+1}+2U_n=0$:
$$U_{k+2}-3U_{k+1}+2U_k=0$$
$$U_{k+2}=3U_{k+1}-2U_k$$
$$U_{k+2}=3(2^{k+1}+1)-2(2^{k}+1)$$
$$U_{k+2}=3\times2^{k+1}+3-2\times2^{k}-2$$
$$U_{k+2}=3\times2^{k+1}-\times2^{k+1}+1$$
$$U_{k+2}=2\times2^{k+1}+1$$
$$U_{k+2}=\times2^{k+2}+1$$
Therefore, the equation is true for $n=k+2$.
Because the equation is true for $n=1$ and $n=2$, and it being true for $m=k$ and $n=k+1$ makes it true for $n=k+2$, it is true for all positive integers $n$.
It's like an infinite line of dominoes, but it takes $2$ dominoes to make the next fall. Because the first $2$ dominoes ($n=1$ and $n=2$) fall (fulfils the equation), then all the dominoes fall (equation is true for all positive integers $n$).
</s>