2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Why do you think you have done something wrong? It looks perfectly okay to me! $\endgroup$ – Prasun Biswas Apr 10 '15 at 15:26
  • 1
    $\begingroup$ $$3\times 2^n=3\times 2^{1+n-1}=3\times 2^1\times 2^{n-1}$$ $\endgroup$ – Prasun Biswas Apr 10 '15 at 15:26
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.