Mathematical Induction with an inequality

**Dave2718** · March 16th 2010, 10:51 PM

Hello, I had this on my exam today, I was positive that I'd be able to deal with inequalities but for some reason this one threw me off. I had to prove

$ \frac{1}{n!} \leq \frac{1}{2^{n-1}} $

for all positive integers i.e n=0,1,2,3..

anyone mind throwing some hints?

**emakarov** · March 17th 2010, 02:50 AM

This holds iff $n!\ge 2^{n-1}$ . To prove this by induction, note that when going from $n$ to $n+1$ , the left-hand side is multiplied by $n+1$ , while the right-hand side is multiplied by $2$ .

In fact, it is not necessary to take reciprocals. The LHS is divided by $n+1$ , and the RHS is divided by 2.

**Archie Meade** · March 17th 2010, 04:29 AM

Originally Posted by Dave2718

Hello, I had this on my exam today, I was positive that I'd be able to deal with inequalities but for some reason this one threw me off. I had to prove

$ \frac{1}{n!} \leq \frac{1}{2^{n-1}} $

for all positive integers i.e n=0,1,2,3..

anyone mind throwing some hints?

0! is defined as 1

$\frac{1}{1}<\frac{1}{2^{-1}}$ as $\frac{1}{2^{-1}}=2$

$\frac{1}{1!}=\frac{1}{2^0}$

$\frac{1}{2(1)}=\frac{1}{2^1}$

$\frac{1}{3(2)}<\frac{1}{2(2)}$

$\frac{1}{4(3)2}<\frac{1}{2(2)2}$

By inspection, the factorial is always increasing more since we are multiplying by values more and more greater than 2.

**novice** · March 17th 2010, 07:35 AM

Originally Posted by Dave2718

Hello, I had this on my exam today, I was positive that I'd be able to deal with inequalities but for some reason this one threw me off. I had to prove

$ \frac{1}{n!} \leq \frac{1}{2^{n-1}} $

for all positive integers i.e n=0,1,2,3.. Zero is not a positive integer.

anyone mind throwing some hints?

It's straight forward.

I will show you the inductive step.

Proof:

We assume $\frac{1}{n!} \leq \frac{1}{2^n-1}$ , and wish to prove $\frac{1}{(n+1)!} \leq \frac{1}{2^{n+1}-1}$ .

By implication it is expressed as

$ \frac{1}{n!} \leq \frac{1}{2^n-1} \Rightarrow \frac{1}{(n+1)!} \leq \frac{1}{2^{n+1}-1} $

So if we can start from $\frac{1}{n!} \leq \frac{1}{2^n-1}$ and end our proof with $\frac{1}{(n+1)!} \leq \frac{1}{2^{n+1}-1}$ , we are home free.

Let's begin with $\frac{1}{n!} \leq \frac{1}{2^n-1}$ . Multiplying through with $\frac{1}{n+1}$ , we obtain

$\frac{1}{(n+1)n!} \leq \frac{1}{(2^n-1)(n+1)}$ . Observe

$\frac{1}{(n+1)!} \leq \frac{1}{n2^n+2^n-n-1}$
$\frac{1}{(n+1)!} \leq \frac{1}{2^n(n+1)-n-1}= \frac{1}{2\cdot 2^n-n-1}\leq \frac{1}{2^{n+1}-2}< \frac{1}{2^{n+1}-1}$

So we succeeded.

**Archie Meade** · March 17th 2010, 11:40 AM

Originally Posted by Dave2718

Hello, I had this on my exam today, I was positive that I'd be able to deal with inequalities but for some reason this one threw me off. I had to prove

$ \frac{1}{n!} \leq \frac{1}{2^{n-1}} $

for all positive integers i.e n=0,1,2,3..

anyone mind throwing some hints?

via induction..

$\frac{1}{n!}\le \frac{1}{2^{n-1}}$ ?

Does the above cause $\frac{1}{(n+1)!}\le \frac{1}{2^n}$ ?

Proof

$\frac{1}{(n+1)!}\le \frac{1}{2^n}\ \Rightarrow\ \left(\frac{1}{n+1}\right)\frac{1}{n!}\le \left(\frac{1}{2}\right)\frac{1}{2^{n-1}}$

When $n\ge\ 2,\ n+1\ge\ 2$

Hence the inequality is true as $\left(\frac{1}{n+1}\right)\frac{1}{n!}\le\ \left(\frac{1}{2}\right)\frac{1}{2^{n-1}}$ if $\frac{1}{n!}\le\ \frac{1}{2^{n-1}}$

and proof of the truth of the inequality is verified for the first n.

**novice** · March 17th 2010, 12:13 PM

Originally Posted by Archie Meade

via induction..

$\frac{1}{n!}\le \frac{1}{2^{n-1}}$ ?

Does the above cause $\frac{1}{(n+1)!}\le \frac{1}{2^n}$ ?

Proof

$\frac{1}{(n+1)!}\le \frac{1}{2^n}\ \Rightarrow\ \left(\frac{1}{n+1}\right)\frac{1}{n!}\le \left(\frac{1}{2}\right)\frac{1}{2^{n-1}}$

When $n\ge\ 2,\ n+1\ge\ 2$

Hence the inequality is true as $\left(\frac{1}{n+1}\right)\frac{1}{n!}\le\ \left(\frac{1}{2}\right)\frac{1}{2^{n-1}}$ if $\frac{1}{n!}\le\ \frac{1}{2^{n-1}}$

and proof of the truth of the inequality is verified for the first n.

Sorry, I wasn't paying attention. Since it's $\frac{1}{2^{n-1}}$ , it should be easier.

Let's see:

$ \begin{aligned} \frac{1}{(n+1)!}&=\frac{1}{2^{n-1}}\cdot \frac{1}{(n+1)}\\ &\leq \frac{1}{2^{n-1}}\cdot \frac{1}{(2)}\\ &\leq \frac{1}{2^n} \end{aligned} $

Yep!

**Dave2718** · March 17th 2010, 02:12 PM

thanks guys, I actually tried the problem after the test before anyone was able to help me out and actually got it pretty much just as all of you did, don't you hate it when that happens?

Thread: Mathematical Induction with an inequality

LinkBack

Thread Tools

Display

Mathematical Induction with an inequality

Similar Math Help Forum Discussions

Mathematical induction

Rigorously prove the principle of complete induction from mathematical induction??

Proof of mathematical induction inequality

mathematical induction for an inequality

mathematical induction...!!!!

Search Tags