Mathematical Induction with an inequality

• Mar 16th 2010, 10:51 PM
Dave2718
Mathematical Induction with an inequality
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?
• Mar 17th 2010, 02:50 AM
emakarov
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.
• Mar 17th 2010, 04:29 AM
Quote:

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.
• Mar 17th 2010, 07:35 AM
novice
Quote:

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.
• Mar 17th 2010, 11:40 AM
Quote:

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.
• Mar 17th 2010, 12:13 PM
novice
Quote:

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!
• Mar 17th 2010, 02:12 PM
Dave2718
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?