Prove by induction on $n$

Question

Prove, by induction, that $n^2+3n\lt2^n$ for all integers $n$ bigger than $5$.

I have done the basis part. For the induction step, I found that $n^2+5n+4$ is less than $2n^2$.

Answer 1

Let's continue from where you were stuck

$$n^2+5n+4\leq2^n\times 2 \Rightarrow n^2+3n+2n+4\leq 2^n +2^n $$

Since $n^2+3n\leq 2^n $:

$$n^2+3n+2n+4\leq 2^n+2n+4 \leq 2^n +2^n \Rightarrow 2n+4 \leq 2^n $$

Since $2n+4 \leq n^2+3n $ if $n\geq 2$: $$ 2n+4 \leq n^2+3n \leq 2^n \Rightarrow n^2+3n \leq 2^n $$

That is our inductive hyphotesis.

:)

Answer 2

For the induction step, you must show $(n+1)^2+3(n+1)<2^{n+1}$ assuming $n^2+3n<2^n.$

Well, if $n^2+3n<2^n$,

then $(n+1)^2+3(n+1)=n^2+5n+4=(n^2+3n)+(2n+4)<2^n+2n+4.$

It remains to show that $2n+4<2^n$,

because then we have $(n+1)^2+3(n+1)<2^n+2^n=2^{n+1}$ and we're done.

That $2n+4<2^n$ is true for $n>5$ could be shown by induction or calculus;

alternatively, we have, for $n>2$, $n(n+2)>2(n+2)$ so $n^2+2n>2n+4,$

so $2n+4<n^2+2n<n^2+3n,$ so, with our induction hypothesis, for $n>5,$ $2n+4<2^n.$