Prove by induction that $u_n=3\times2^{n-1}-1$ for all $n\ge1$

Question

The sequence $u_1$, $u_2$, $u_3$,... is defined by $$u_1=2\,,\,\,\,\,\,\,\,\,\,u_{k+1}=2u_k+1$$ Prove by induction that, for all $n\ge1$, $$u_n=3\times2^{n-1}-1$$ You first have to prove that $u_1=2$ $$u_1=3\times2^{1-1}-1=3\times1-1=2$$ Then if I am correct you assume that $n=k$? $$u_n=u_k$$ $$\implies u_{n+1}=2\color{red}{u_n}+1$$ $$\implies u_{n+1}=2\color{red}{(3\times2^{n-1}-1)}+1$$ $$u_{\color{green}{n+1}}=3\times2^{(\color{green}{n+1})-1}-1$$ So now you're left with $$3\times2^{(n+1)-1}-1=2(3\times2^{n-1}-1)+1$$ $$3\times2^n-1=2\times3\times2^{n-1}-1$$ Now I have to prove that $$3\times2^n=2\times3\times2^{n-1}$$ What have I done wrong? Regards Tom

Answer 1

Everything is correct.$$2\cdot 3\cdot 2^{n-1}-1=3\cdot 2^n-1$$

Answer 2

Mostly this is fine, but the start of your inductive step should be that you assume not that $n=k$ but that the statement to be proved is true for a particular value ($k$) of the generic $n$. You then use this assumption to show that the truth of the same statement for $n=k+1$ is logically a consequence of the truth of the assumed statement. Combined with the base case (here $n=1$) this gives us a nice ascending ladder of cases from $n=1$ all the way up the positive integers.