Use proof by induction to prove $ \frac{1}{n!}<\frac{1}{2^n-1} $ for all $n\geq 4$

Question

Use proof by induction to prove that that $ \frac{1}{n!}<\frac{1}{2^n-1} $ for all $n\geq 4$, .\Base case: $$\frac{1}{4}=\frac{1}{24}\leq \frac{1}{2^4-1}$$ Inductive hypothesis: Assume there exists $k\in \mathbb{N}$ s.t.

$$ \frac{1}{k!}\leq\frac{1}{2^k-1} $$ Inductive step: Show that:$$ \frac{1}{(k+1)!}\leq\frac{1}{2^{k+1}-1} $$ Now, $$\frac{1}{(k+1)!}=\frac{1}{k!}\cdot\frac{1}{k+1}$$ Using the hypothesis $$\frac{1}{(k+1)!}\leq\frac{1}{2^k-1}\cdot \frac{1}{k+1}$$ Because $n\geq4, \frac{1}{k+1}<\frac{1}{2}$ $$\frac{1}{(k+1)!}\leq\frac{1}{2^k-1}\cdot \frac{1}{2}=\frac{1}{2^{k+1}-2}\leq\frac{1}{2^{k+1}-1}$$ Hence by mathematical induction we have proved that $ \frac{1}{n!}<\frac{1}{2^n-1} $ for all $n\geq 4$

Firstly I need to know if the proof is correct, secondly it has to be as concise as possible hence I would like to know if there are any lines I can change/delete

And lastly can anyone explain to me why every sentence starts with "\" It looks perfectly fine in www.sharelatex.com ;(

Answer 1

All in all it looks like you have the idea down on how induction works. It looks like you are correctly making the induction step to get your result. I have a couple things to point out, however.

$(1)$ During your induction step you introduce the "$\geq$" symbol, when initially you are trying to write a proof about a strict inequality (which should only use the "$>$" symbol). If the strict inequality holds, it is not incorrect to use "$\geq$", but for the sake of consistency you should just use one.

$(2)$ Your induction hypothesis is not stated quite right. It is not enough to assume there exists $k \in \Bbb{N}$ such that the inequality holds. You want to make the stronger assumption that you can find this $k$, and the inequality holds for all $n \leq k$. It is in doing this that you will be allowed to conclude at the end of the proof that the inequality holds for all $n \geq 4$, instead of just $n=4$, and one arbitrary $k$.

$(3)$. If you are looking for a more concise proof, I would instead prove the equivalent statement that $2^n-1<n!$ for all $n \geq 4$. It is clear for $n \geq 4$ that $$2^n-1<2^n = 2 \cdot 2\cdot 2\cdot 2\cdot \ldots < 1 \cdot 2\cdot 3 \cdot 4 \cdot \ldots = n!$$ This is easier than dealing with fractions. But, upon proving this result one need merely flip the inequality around and put the quantities on each side under a numerator of $1$.

Answer 2

It's much easier proving that $2^n<1+n!$, for $n\ge4$, which is completely equivalent to your assignment. The base step is obvious. Suppose it holds for $n$; then $$ 2^{n+1}=2\cdot2^n<2\cdot(1+n!)=2+2\cdot n!<1+(n-1)\cdot n!+2\cdot n!=1+(n+1)! $$ because $(n-1)n!>1$.

You can, if you want, transform this into a proof of your assigned inequality, but it's not necessary.

Answer 3

Rewrite as$$n!\ge2^n.$$ Then $$4!\ge2^4$$ and $$n!\ge2^n\land n+1\ge2\implies(n+1)!\ge2^{n+1}.$$