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

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 ;(

• You must start with $n=4$. – User3101 Feb 18 '15 at 16:11
• I see and I am lost know because it is a question copied from the coursework given by a professor, I just blindly followed so lets assume $n\geq4$ – Scavenger23 Feb 18 '15 at 16:12
• So I should say Assume that $\frac{1}{k!}\leq\frac{1}{2^k-1}$ holds for some $k\geq4$ and then proceed ? – Scavenger23 Feb 18 '15 at 16:21
• One error I notice in your logic - in the last statement you state that $\frac 1{2^{k+1}-2} \leq \frac 1{2^{k+1}-1}$. This is incorrect. The latter (-1) fraction has a larger denominator than the -2 fraction, which means it's a smaller fraction. – Duncan Feb 18 '15 at 16:34

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

• Never mind (4). in the preview mode every sentence had "\" in front of it while in here as you see Everything is fine. I see the mistake $< and \leq$ thank you for pointing it out. Thank you. I started induction only 2 weeks ago and it is a difficult topic for me. – Scavenger23 Feb 18 '15 at 16:37
• You see I didn't have the "flipping the fractions" tool in the toolbox so I didn't even think about what you have done in (3). The grammar unfortunately will remain an issue, since English is not my native language. – Scavenger23 Feb 18 '15 at 16:42
• You know what now I realised the whole mistake. I can't copy correctly. The question is not asking to prove $\frac{1}{n!}<\frac{1}{2^n-1}$ but $\frac{1}{n!}<\frac{1}{2^{n-1}}$ – Scavenger23 Feb 18 '15 at 16:50
• I don't want to use you but if I finish the right question this time, would you be able to have a one last look on it? I will stop spamming now since the website tells me to avoid extended discussions in comments. – Scavenger23 Feb 18 '15 at 16:54
• Use proof by induction to prove that that $\frac{1}{n!}<\frac{1}{2^n-1}$ for all $n\geq 3$\\I will use the fact that $k!>2^{k-1}$ is an equivelant statement to $\frac{1}{k!}<\frac{1}{2^k-1}$ .\\Base case $3!>2^{2}$ Inductive step: Assume $k!>2^{k-1}$ holds for all $n\leq k$ for some $k \in \bbb{N}$\\\ Inductive hypothesis\\Show that $(k+1)!>2^k$\\It is clear that when $k\geq 3$\\$2^{k-1}<2^k=2*2*2*2...<1*2*3*4...=k!<(k+1)!$ – Scavenger23 Feb 18 '15 at 17:18

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.

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