0

Prove by mathematical induction that $\frac{n^3}{n!} < \frac{1}{2^n}$ for some $n\geq m$ where $m > 0$

To start off, I assume the hypothesis that it is true for $n$.
Trying to prove for $n+1$, $$\frac{1}{2^{n+1}} - \frac{(n+1)^3}{(n+1)!} > 0.$$

Therefore,

$$\frac{1}{2^{n+1}} - \frac{(n+1)^3}{(n+1)!} = \frac{1}{2^n} \times \frac{1}{2} - \frac{(n+1)^3}{(n+1)!} > \frac{1}{2} \times \frac{n^3}{n!} - \frac{(n+1)^3}{(n+1)!} = \frac{1}{2n!} [ n^3 - 2n^2 - 4n - 2]$$

So basically, my task now is to prove that the last term is greater than $0$. Am i on the right track and how do I go further?

iykwim08
  • 11
  • 2
    Pleas use the title as a summary and the body for the question. Also , show some effort , please. – Peter Sep 14 '23 at 06:02
  • As a starting point, find an integer $m>0$ that satisfies the inequality. It will be the base case. – Gonçalo Sep 14 '23 at 06:18
  • 1
    @Peter sorry, I did not know. I have made ammends to my post. – iykwim08 Sep 14 '23 at 06:21
  • @Gonçalo the number m is a variable. Even if it is the base case, how do I use it while proving my hypothesis? – iykwim08 Sep 14 '23 at 06:22
  • Once you have found $m$, you will be able to show that $n^3-2n^2-4n-2>0$ for all $n\geq m$. – Gonçalo Sep 14 '23 at 06:26
  • @Gonçalo They should look for an $k$ where $n^3 - 2n^2 - 4n - 2 > 0$ for all $n \ge k$. Then, they should find some $m \ge k$ where $m^3/m! < 1/2^m$ (which would be the base case). For $n \ge m$, by the induction argument, the result would be proven. – Theo Bendit Sep 14 '23 at 06:33
  • 2
    @iykwim08 Another similar method, which should be slightly easier in this case, would be to divide, rather than subtract. That is, look at $(n^3/n!)/(1/2^n) = (2^nn^3)/n!$, and see if you can show it's less than $1$. – Theo Bendit Sep 14 '23 at 06:37
  • At the risk of being a curmudgeon, as stated this is trivial and requires no induction, just let $m=1$ and let $n$ be the first positive number you can find that satisfies the inequality. (Yes, I can guess what the statement should be, but that really shouldn't be necessary to do that). – M W Sep 14 '23 at 07:08
  • @MW It is not hard, but it is not really trivial, right? You need to prove existence of such an $n$, which amounts essentially to show the base case :) – Severin Schraven Sep 14 '23 at 07:39
  • @SeverinSchraven touché, I guess I should not go and gripe about someone's problem statement and be imprecise in said griping. – M W Sep 14 '23 at 07:49
  • @MW I was mainly concerned about me not seeing how it becomes trivial after careful rereading. On this level it is imho better to err on the side of pedantry. So, I'd side with you on straightening out the statement. – Severin Schraven Sep 14 '23 at 08:04

1 Answers1

3

Proof by indution:

As the base case, let's take $m=10$: $$ \frac{10^3}{10!}-\frac{1}{2^{10}}\approx -7.0\times 10^{-4}\implies \frac{10^3}{10!}<\frac{1}{2^{10}}. $$ Now, supposing the inequality is true for $n\geq 10$, let's prove that it is also true for $n+1$. Indeed, \begin{align} \frac{(n+1)^3}{(n+1)!}&=\frac{(n+1)^2}{n^3}\frac{n^3}{n!} &\phantom{}\\ &<\left(\frac{1}{n}+\frac{2}{n^2}+\frac{1}{n^3}\right)\frac{1}{2^n}&[\text{by the induction hypothesis}] \\ &\leq\left(\frac{1}{10}+\frac{2}{10^2}+\frac{1}{10^3}\right)\frac{1}{2^n}&[\text{because $n\geq 10$}] \\ &<\frac{1}{2^{n+1}}. \quad{\square} &[\text{because $(\ldots)<1/2$}] \end{align}

Gonçalo
  • 9,312
  • 2
    I now understand how to approach it. I was getting stuck in the third step continuously where you just replaced the n by 10. I did'nt realise the direct substitution would work out in helping me solve the sum. This makes a lot of sense now.

    Thank you very much!

     – iykwim08 Sep 14 '23 at 18:18