# Thread: Mathematical Induction with an inequality

1. ## 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?

2. 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.

3. 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.

4. 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.

5. 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.

6. 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!

7. 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?