The question asks:

Let $a_n$ be the sequence given by $a_1 = 3$ and $a_{n+1} = 2a_n$ + 5 .

Use induction to prove that $a_n \gt 2^n$ for all $n \in \mathbb N$ .

I proved the base case and for the induction step I proved it like so:

\begin{align} a_{k+1} &\gt 2^{k+1}\\ 2a_{k}+5 &> 2^{k+1} \tag{from the original problem}\\ a_{k} &> 2^{k} - (5/2) \end{align}

and because

$$2^k \gt 2^{k} - \frac{5}{2}$$

I finalized my proof.

Is this correct?

  • 1
    $\begingroup$ No, since you assumed $a_{k+1} \gt 2^{k+1}$. You should be starting from the LHS or RHS and use the inductive assumption $a_k \gt 2^k$ to deduce $a_{k+1} \gt 2^{k+1}$. $\endgroup$ – Landuros Apr 7 at 2:10
  • $\begingroup$ Welcome to MSE. Did you mean $a_{n+1}=2a_n+5$? If so, write {$n+1$} $\endgroup$ – J. W. Tanner Apr 7 at 2:22

Your induction step, as I commented, is incorrect because you have started with the very statement you are trying to prove! To avoid this mistake, either start with the LHS or RHS of the equation to deduce the final statement.

Don't forget the inductive assumption is $a_{k}\gt 2^k$.

Your proof might look something like this:

\begin{align} LHS & = a_{k+1}\\ &=2a_k +5 \\ & \gt2\cdot2^k+5 \tag{by the inductive assumption}\\ & =2^{k+1}+5\\ &\gt2^{k+1}\\ &= RHS \end{align}

$\therefore LHS \gt RHS \implies a_{k+1}\gt 2^{k+1}$. The inductive step is done so the induction is completed.

  • $\begingroup$ thanks. but why do you change from = to >? $\endgroup$ – ph-quiett Apr 7 at 3:06
  • $\begingroup$ also I don't get how the proof flows $\endgroup$ – ph-quiett Apr 7 at 3:13
  • $\begingroup$ I change it from $=$ to $\gt$ because the next line is less than the current line, if that makes sense. To get a better idea on how induction proofs work, just do a search on google. $\endgroup$ – Landuros Apr 8 at 9:32

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.