1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ You must start with $n=4$. $\endgroup$ – User3101 Feb 18 '15 at 16:11
  • $\begingroup$ 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$ $\endgroup$ – Scavenger23 Feb 18 '15 at 16:12
  • $\begingroup$ So I should say Assume that $\frac{1}{k!}\leq\frac{1}{2^k-1}$ holds for some $k\geq4$ and then proceed ? $\endgroup$ – Scavenger23 Feb 18 '15 at 16:21
  • $\begingroup$ 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. $\endgroup$ – Duncan Feb 18 '15 at 16:34
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Scavenger23 Feb 18 '15 at 16:37
  • $\begingroup$ 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. $\endgroup$ – Scavenger23 Feb 18 '15 at 16:42
  • $\begingroup$ 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}}$ $\endgroup$ – Scavenger23 Feb 18 '15 at 16:50
  • $\begingroup$ 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. $\endgroup$ – Scavenger23 Feb 18 '15 at 16:54
  • $\begingroup$ 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)!$ $\endgroup$ – Scavenger23 Feb 18 '15 at 17:18
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.