5
$\begingroup$

Step one: for case where $n=6$

$$7n <2^n$$ $$7(6)<2^6 \rightarrow 42<64$$.

Step two: Suppose for $n$ such that $7n<2^n$ is true. Now prove for $n+1$

$$(2)7n<(2)2^n$$ $$14n<2^{n+1}$$

But since $n<7n<2^n$, then $n+7<7(n+1)<2^n+7<2^{n+1}(?)$.

Then $7(n+1)<2^{n+1}$

I'm new in this induction process, so any help/tips for this problem would be really appreciated.

$\endgroup$
1
  • 1
    $\begingroup$ From $14n<2^{n+1}$, you'd want to show that $7(n+1)\leq 14n$, and then you are done. But that is easy to prove if $1\leq n$ since then $7\leq 7n$ and then, adding $7n$ to both sides gives you $7(n+1)=7n+7\leq 7n+7n=14n$. $\endgroup$ Aug 27, 2017 at 15:08

6 Answers 6

7
$\begingroup$

We will prove the assertion by induction on $n$.


The assertion is true for $n=6$. $\checkmark$
Suppose that the assertion is true for $k=n$; $\color{Blue}{7n<2^n}$.
on the otherhand we know that $\color{Red}{7}<42\leq7n<\color{Red}{2^n}$; so we have :
$$ \color{Green}{7(n+1)}= \color{Blue}{7n} + \color{Red}{7} < \color{Blue}{2^n} + \color{Red}{2^n} = \color{Green}{2^{n+1}} ,$$ so the assertion is true for $\color{Green}{k=n+1}$.

$\endgroup$
5
$\begingroup$

You made a very good begin.

I only don't see why you need $n+7 < 7(n+1)$.
You just need $7(n+1) < 2^n+7 < 2^{n+1}$ and you are done.

You marked $2^n+7 < 2^{n+1}$ with a question mark. It is certainly something you should prove. In general, when you don't immediately see why something is true, you have to prove it. You can do this by subtracting $2^n$ from both sides. Since you ask for a hint, I hid the complete answer below.

Since $n\geq 6$, we have $2^n \geq 64 > 7$, so $2^n+7 < 2^n + 2^n = 2^{n+1}$.

$\endgroup$
4
$\begingroup$

$$2^n-7n=(1+1)^n-7n>1+n+\frac{n(n-1)}{2}+\frac{n(n-1)(n-2)}{6}-7n=$$ $$=\frac{n^3-37n+6}{6}=\frac{(n-6)(n^2+6n-1)}{6}\geq0.$$ Done!

$\endgroup$
3
$\begingroup$

you have to show: $$2^{n+1}>7(n+1)$$ multiplying $$2^n>7n$$ by $2$ we get $$2^{n+1}>14n$$ and it is $$14n>7n+7$$ and this is true since $$n\geq 6$$

$\endgroup$
3
$\begingroup$

$2^n=(1+1)^n=2+2n+n(n-1)+f(n)>n(n+1)$, since $f(n)>0$, for $n\geq 3$

Since $n\geq 6$, we have $2^n>n(n+1)\geq 7n\space\space\space\blacksquare$

$\endgroup$
8
  • $\begingroup$ It is not clear this really holds for $n\geq6$, only for sufficiently large $n$. $\endgroup$
    – wythagoras
    Aug 27, 2017 at 15:05
  • $\begingroup$ @wythagoras is it ok now? $\endgroup$
    – MAN-MADE
    Aug 27, 2017 at 15:09
  • 1
    $\begingroup$ Well, if this was a test, I would not give full marks for this answer. I'd add something like: when $n\geq 3$, there are more terms in this expansion that are all positive, so $f(n) > 0$. But then it is a very interesting approach (+1), but I would not recommend the asker to use this kind of argument now. $\endgroup$
    – wythagoras
    Aug 27, 2017 at 15:12
  • $\begingroup$ @wythagoras thanks, I think this is more generalised version(may be I am wrong), this proves that $2^n>n(n+1)$, then, for $n\geq 3$, $2^n>4n$ or if $n\geq 100$, $2^n>101n$, etc. $\endgroup$
    – MAN-MADE
    Aug 27, 2017 at 15:31
  • $\begingroup$ can you tell me what should I write to make it perfect!!! $\endgroup$
    – MAN-MADE
    Aug 27, 2017 at 15:31
2
$\begingroup$

You are interested in showing that

$$2^{n}+7 < 2^{n+1}=2(2^n)$$

which is equivalent to $7 < 2^n$ which is is true for $n \geq 6$.

Remark:

$\color{blue}{n < } 7n < 2^n $ and the two lines above the question mark seems redundant.

$\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.