I saw a problem online (Orig) as follows. I'm curious if there's a straightfoward way to prove it using induction.  It's easy to prove that (Orig) holds when $n=1$ or $m=1$ , which seems like a good way to set up base cases, but I'm stuck on where to go from there.  For all positive integers $m, n$, show that the following inequality (Orig) holds:  $$ \left|\sqrt{2} - \frac{m}{n}\right| &gt; \frac{1}{3n^2} \tag{Orig} $$  Note that (Orig) is equivalent to (201) below, because the LHS is irrational and the RHS is rational:  $$ \left|\sqrt{2} - \frac{m}{n}\right| \ge \frac{1}{3n^2} \tag{201} $$  I suspect there's probably a general result about best rational approximations to an irrational number like $\sqrt{2}$ or something using the convergents of the continued fraction representation of $\sqrt{2}$ (101) . (Orig) feels like a statement of how well you can approximate $\sqrt{2}$ with rational numbers, but I don't know whether the $\frac{1}{3n^2}$ bound is tight or not.  $$ \sqrt{2} = 1 + \cfrac{1}{2           + \cfrac{1}{2           + \cfrac{1}{2 + \cfrac{1}{2 + \cdots}}}} \tag{101} $$  I have some base cases as follows, $n=m=1$ (102); $n=1, m &gt; 1$ (109); $n&gt;1, m=1$ (117).  $$ \left| \sqrt{2} - \frac{m}{n} \right| \ge \frac{1}{3n^2} \;\;\;\text{when $n = m = 1$} \tag{102} $$  And the proof of (102).  $$ \left| \sqrt{2} - 1 \right | &lt; \frac{1}{3} \tag{NG1} $$ $$ \sqrt{2} - 1 &lt; \frac{1}{3} \tag{104} $$ $$ \sqrt{2} &lt; \frac{4}{3} \tag{105} $$ $$ 4 &lt; \frac{16}{9} \tag{106} $$ $$ 36 &lt; 16 \tag{107} $$ $$ \bot \tag{108} $$  And the next case (109)  $$ \left| \sqrt{2} - \frac{m}{n} \right| \ge \frac{1}{3n^2} \;\;\;\text{when $n = 1, m \ge 2$} \tag{109} $$  The expression inside the absolute value on the LHS of (109) is always negative (NG2).  $$ m - \sqrt{2} &lt; \frac{1}{3} \tag{NG2} $$ $$ m &lt; \frac{1}{3} + \sqrt{2} \tag{111} $$  We know that $2 \le m$, so we can infer the following.  $$ 2 &lt; \frac{1}{3} + \sqrt{2} \tag{112} $$  $$ 6 &lt; 1 + 3\sqrt{2} \tag{113} $$  $$ 5 &lt; 3\sqrt{2} \tag{114} $$  $$ 25 &lt; 18 \tag{115} $$  $$ \bot \tag{116} $$  And the next case (117)  $$ \left| \sqrt{2} - \frac{1}{n} \right| \ge \frac{1}{3n} \;\;\;\text{where $m = 1$, $n \ge 2$} \tag{117} $$  $\frac{1}{n}$ is at most one, so the expression inside the absolute value on the LHS is positive.  $$ \sqrt{2} - \frac{1}{n} &lt; \frac{1}{3n} \tag{NG3} $$  $$ \sqrt{2} &lt; \frac{1}{3n} + \frac{1}{n} \tag{119} $$  $$ \sqrt{2} &lt; \frac{4}{3n} \tag{120} $$  $$ 3n\sqrt{2} &lt; 4 \tag{121} $$  $$ 3n &lt; 2 \sqrt{2} \tag{122} $$  $$ 9n^2 &lt; 8 \tag{123} $$  however, $n \ge 2$ by hypothesis.  $$ 36 &lt; 8 \tag{124} $$  $$ \bot \tag{125} $$
16666
Prove that for for all $p,q\in \mathbb{Z}$, $q&gt;0$ we have: $$ \left| \sqrt{2}-\frac{p}{q} \right| &gt; \frac{1}{3q^2}. $$  To be honest, I do not know where to start - any help would be appreciated.
45633
I'm reading R. Courant &amp; H. Robbins'  for fun. I'm on page $60$ and $61$ of the second addition. There are three exercises on proving numbers irrational spanning these pages, the last is as follows.     Exercise $3$: Prove that $\phi=\sqrt{2}+\sqrt{3}+\sqrt{5}$ is irrational. Try to make up similar and more general examples.   My Attempt:     Lemma: The number $\sqrt{2}+\sqrt{3}$ is irrational. (This is part of Exercise 2.)   Proof: Suppose $\sqrt{2}+\sqrt{3}=r$ is rational. Then $$\begin{align} 2&amp;=(r-\sqrt{3})^2 \\ &amp;=r^2-2\sqrt{3}+3 \end{align}$$ is rational, so that $$\sqrt{3}=\frac{r^2+1}{2r}$$ is rational, a contradiction. $\square$  Let $\psi=\sqrt{2}+\sqrt{3}$. Then, considering $\phi$, $$\begin{align} 5&amp;=(\phi-\psi)^2 \\ &amp;=\phi^2-\psi\phi+5+2\sqrt{6}. \end{align}$$  I don't know what else to do from here. My plan is/was to use the Lemma above as the focus for a contradiction, showing $\psi$ is rational somehow.  Please help :)  Thoughts:  The "try to make up similar and more general examples" bit is a little vague.    The question is not answered  as far as I can tell.
51490
I stumbled on the following inequality: For all $n\geq 1,$ $$2\sqrt{n+1}-2\sqrt{n}&lt;\frac{1}{\sqrt{n}}&lt;2\sqrt{n}-2\sqrt{n-1}.$$ However I cannot find the proof of this anywhere. Any ideas how to proceed?  Edit: I posted a follow-up question about generalizations of this inequality here:
62463
So I have to prove the following using induction.  ${\displaystyle \prod_{i=2}^{i=n} \left(1-\frac{1}{i^2}\right)} = \frac{n+1}{2n}$  I showed the basis step that if $n=i=2$, then the two functions are equal $\frac{3}{4}$, and I know that the induction step involves simplifying the function where $n=n+1$. But I'm not sure how to do it with the following algorithm. I am quite confused. Can someone show me how I can prove this in the induction step?
69440
Show by induction that for all natural numbers n>3  $(1+\frac{1}{n})^n&lt;n$  Let $(1+\frac{1}{n})^n&lt;n$ be true !   We show that $(1+\frac{1}{n+1})^{n+1})&lt;n+1$  $(1+\frac{1}{n})^n(1+\frac{1}{n})&lt;n(1+\frac{1}{n})$   $(1+\frac{1}{n})^{n+1}&lt;n+1$  So now we just need to show that   $(1+\frac{1}{n+1})^{n+1}&lt;(1+\frac{1}{n})^{n+1}$  So here , If I show that :   $(1+\frac{1}{n+1})&lt;(1+\frac{1}{n})$   Does that mean im done with exercise ?
96688
My question concerns the inductive step of the proof below. I've typed out the work I've done so far. If anyone has any suggestions on how to proceed thanks in advance.  If $n\in\mathbb{N}$, then $(1-\frac{1}{2})(1-\frac{1}{4})(1-\frac{1}{8})(1-\frac{1}{16})\cdots(1-\frac{1}{2^n})\ge\frac{1}{4}+\frac{1}{2^{n+1}}$.  $Proof.$ We use mathematical induction.  Base Case. For $n=1$ we see that $1-\frac{1}{2}\ge\frac{1}{4}+\frac{1}{4}$ since $\frac{1}{2}\ge\frac{1}{2}$.  Inductive Step. Let $n&gt;1$. Assume our statement is true for $n$. Now observe that  $\begin{align}(1-\frac{1}{2})(1-\frac{1}{4})(1-\frac{1}{8})(1-\frac{1}{16})\cdots(1-\frac{1}{2^{n+1}})&amp;\ge\\ \left((1-\frac{1}{2})(1-\frac{1}{4})(1-\frac{1}{8})(1-\frac{1}{16})\cdots(1-\frac{1}{2^{n}})\right)(1-\frac{1}{2^{n+1}})&amp;\ge(\frac{1}{4}+\frac{1}{2^{n+1}})(1-\frac{1}{2^{n+1}}) \end{align}$  My question is: How do we get from $\begin{align} (\frac{1}{4}+\frac{1}{2^{n+1}})(1-\frac{1}{2^{n+1}}) \end{align}$ to $\frac{1}{4}+\frac{1}{2^{(n+1)+1}}$?  Most of what I've attempted has led to tedious calculations that do not simplify to the desired result. I've also tried making the argument that $(1-\frac{1}{2^{n+1}})$ must be $\ge$ to $\frac{1}{2}$ but then I'm stuck with $\frac{1}{8}+\frac{1}{2^{(n+1)+1}}$... Is my approach incorrect here?
11543
I need to prove the inequality ${M}\choose{N_1}$ ${M}\choose{N_2}$ $\leq$ ${2M}\choose{N_1+N_2}$ for $M, N_1, N_2 \in \mathbb{N},\,M\geq N_1,N_2$. I wanted to prove it by induction. But since we are given 3 variables running, I was confused if the natural induction, as I know it, can be used in this case. Can you tell me if proving by induction is possible and necessary in this example ? We get $N_1, N_2, N_1+N_2$ fractions from ${M}\choose{N_1}$,${M}\choose{N_2}$, and ${2M}\choose{M_1+M_2}$, respectively. Without loss of generality, we assume $N_1\geq N_2.\,$An appropriate approximation of all fractions from left to right leads to: $$ \frac{M}{N_1}\frac{M-1}{N_1 -1}\frac{M-2}{N_1-2}\cdots \frac{M-(N_1-1)}{1} \cdot\frac{M}{N_2}\frac{M-1}{N_2 -1}\frac{M-2}{N_2-2}\cdots \frac{M-(N_2-1)}{1}\leq \frac{2M}{N_1+N_2}\cdots $$ For the second fraction from the left I get: $\frac{M-1}{N_1 -1}=\frac{2M-2}{2N_1-2}\geq\frac{2M-1}{2N_1-1}\leq\frac{2M-1}{N_1+N_2-1}.$ The last term in the last inequality is not the convenient approximation for $\frac{M-1}{N_1 -1}$ unless we got $\leq$ instead of $\geq$ sign in the last inequality. Can somebody provide some hint how to go further ? Thanks.
60014
Let $x_1$, $x_2$, $\ldots$, $x_n$ be positive real numbers, and let $$S=x_1+x_2+\cdots+x_n.$$ Prove that $$(1+x_1)(1+x_2)\cdots(1+x_n)\leq 1+S+\frac{S^2}{2!}+\frac{S^3}{3!}+\cdots+\frac{S^n}{n!}.$$  My first thought is about using induction. For $n=1$, $LHS=1+x_1\leq1+S=RHS$. Now I suppose that this inequality holds true for $n=k$; that is, $$(1+x_1)(1+x_2)\cdots(1+x_k)\leq 1+S+\frac{S^2}{2!}+\frac{S^3}{3!}+\cdots +\frac{S^k}{k!}.$$ And here I am stuck. I can't really see how I can find the relation between when $n=k$ and $n=k+1$. Perhaps induction may not be the way?  Any hints or suggestions will be much appreciated. Thanks.
117390
I'm working on a problem that's given me the run around for about a weekend. The statement:  For all $m$ greater than or equal to $2$ and for all $n$ greater than or equal to $0$, $m - 1$ divides $m^n - 1$.  Using induction over $n$, the base step comes easy since $m^n - 1$ is $0$ when $n = 0$.  My induction hypothesis is letting $k \geq 0$ and assuming that $m - 1$ divides $m^k - 1$. In order to show that $m - 1$ divides $m^{k+1} - 1$, I obviously need to use the induction hypothesis. However, no matter where I try to use the fact that $m^k - 1 = (m-1)a$ for some $a$ in the integers, the expression $m^{k+1} - 1$ always becomes more difficult to get to $m^{k+1} - 1$ being equal to $(m-1)b$ for some $b$ in the integers.   In other words, I can't figure out any actually helpful way to apply the induction hypothesis with the goal of proving the next step.  Any help would be appreciated!
72726
I have seen this problem in a book .   But I don't know what should be the solution . Question is   There is a sequence defined by $$\sqrt[1]{1},\sqrt[2]{2},\sqrt[3]{3},\sqrt[4]{4},\cdots,\sqrt[n-1]{n-1},\sqrt[n]{n}$$  We have to find the largest number in this sequence.  What I did is as usual what I do when comparing two irrational numbers  I compared $\sqrt[1]{1} $ &amp; $\sqrt[2]{2}$ and found that $\sqrt[2]{2}$ is greater.  Then I compared $\sqrt[3]{3} $ &amp;$\sqrt[2]{2}$ and found $\sqrt[3]{3}$ is greater.  Then I compared $\sqrt[3]{3} $&amp; $\sqrt[4]{4}$ and found $\sqrt[3]{3}$ is greater.  And then I compared  $\sqrt[5]{5}$&amp;$\sqrt[4]{4}$ and found $\sqrt[4]{4}$ is greater.  And finally I compared $\sqrt[5]{5}$&amp;$\sqrt[6]{6}$ and found $\sqrt[5]{5}$ is greater.  I cannot guarantee will it work up to infinity or not and found $\sqrt[3]{3}$ is greatest term.  And now I have to prove my result.  More generally I have to prove that $\sqrt[n]{n}\gt \sqrt[n+1]{n+1}$ for all $n\in\mathbb N$ and $n\gt 2$  I applied induction to prove it but didn't got the solution.  Please help me in proving this .  Or please tell me an alternative way to tell which number is largest in the sequence.
104310
I need to prove that for every natural n that happens and the prove needs to be by induction, I wont prove for n=1 because its obvious,so lets move to n and n+1 $$ \frac{(2n!)}{(n!)^2} ≥ \frac{(4^n)}{(2n+1)} $$ the assumption for n+1 $$ \frac{(2n+2)!}{(n+1)!^2} ≥ \frac{(4^{n+1})}{2n+3} $$ now I dont now how to progress,I tried this for n+1 $$ \frac{(2n+2)(2n+1)(2n!)}{(n+1)!^2} ≥ \frac{(4^{n}4^1)}{(2n+1)+2)} $$ and had a suggestion to use $ 2n! = (n!) \prod _{n=n}^{2n}\:n\cdot )! $ but cant see how it helps,ty.
72107
For $n \geq 2$ prove that $(1- \frac{1}{4})(1- \frac{1}{9})(1- \frac{1}{16})...(1- \frac{1}{n^2}) = \frac{n+1}{2n}$  We need to use induction.   The Principle of Mathematical Induction, Theorem 4.2.1, states that $n_0 \in \mathbb{Z}$. For each integer $n \geq n_o$, let $P(n)$ be a statement about $n$. Suppose that the following two statements are true:   $P(n_o)$ $( \forall n \geq n_o)[P(n) \rightarrow P(n+1)]$   Then, for all integers $n \geq n_o$, that statement $P(n)$ is true.  Suppose,  $(1- \frac{1}{4})(1- \frac{1}{9})(1- \frac{1}{16})...(1- \frac{1}{n^2}) = \frac{n+1}{2n}$, the equation, is true for some natural number $k$.  $\frac{1}{2^2})*...*(1- \frac{1}{k^2}) = \frac{k+1}{2k}$  The induction hypothesis $P(k) \rightarrow P(k+1)$ must hold for any natural number $k, P(k),$ from the basis and inductive step.  $(\frac{1}{2^2})*...*(1- \frac{1}{k^2})*(1- \frac{1}{(k+1)^2}) = \frac{k+1}{2k}(1- \frac{1}{(k+1)^2})$  $\leftrightarrow$ $\frac{k+1}{2k}(\frac{(k+1)^2}{(k+1)^2}- \frac{1}{(k+1)^2})$  $\leftrightarrow$ $(\frac{(k+1)}{2k})( \frac{(k+1)^2-1}{(k+1)^2})$  $\leftrightarrow$ $( \frac{(k^2+2k+1-1}{(2k)(k+1)})$  $\leftrightarrow$ $( \frac{(k^2+2k}{(2k)(k+1)})$  $\leftrightarrow$ $( \frac{k+2}{(2)(k+1)})$  We need to demonstrate that   $(\frac{1}{2^2})*...*(1- \frac{1}{n^2}) = \frac{n+1}{2n}$  holds true for $n \geq 2$  The question is do I just substitute a number that is greater than two after I did the induction?
79185
Assumption: $\sqrt{1}+\sqrt{2}+\sqrt{3}+...+\sqrt{k}\ge\frac{2}{3}k\sqrt{k}$   Prove true for $n=k+1$ $$\sqrt{1}+\sqrt{2}+\sqrt{3}+...+\sqrt{k}+\sqrt{k+1}\ge\frac{2}{3}(k+1)\sqrt{k+1}$$  I'm upto :$$\sqrt{1}+\sqrt{2}+\sqrt{3}+...+\sqrt{k}+\sqrt{k+1}\ge\frac{2}{3}k\sqrt{k}+\sqrt{k+1}$$after which I'm stuck.
101647
I'm working on proving the following statement using induction:  $$ \sum_{r=1}^n \frac{1}{r^2} \le \frac{2n}{n+1} $$  Fair enough. I'll start with the basis step:  Basis Step: (n=1) $$ \sum_{r=1}^n \frac{1}{r^2} \le \frac{2n}{n+1} $$ $$ \frac{1}{1^2} \le \frac{2}{1+1} $$ $$ 1 \le 1  \checkmark  $$  Inductive Step: $$ \sum_{r=1}^{n+1} \frac{1}{r^2} \le \frac{2(n+1)}{(n+1)+1} $$ $$ \sum_{r=1}^{n+1} \frac{1}{r^2} \le \frac{2(n+1)}{n+2} $$  My goal is to prove $\forall_{n\ge1} s(n) \implies s(n+1) $ or that this inequality holds true for all $n\ge1$.  I'm not quite sure to go from here on the inductive step. I understand that I need to basically work some clever substitution and manipulation into the problem to end up with: $$ \sum_{r=1}^{n+1} \frac{1}{r^2} \le \frac{2n}{n+1} $$  However, I'm not quite sure what needs to done to obtain this after attempting a few times.
123027
I am having trouble with my homework problem, it says:      Suppose that $n$ is a positive integer and that $x &gt; 0$. Show that   $$\left(1+\frac{x}{n}\right)^n &lt; e^x.$$    I have proved the base case, but I am unsure how to proceed with the induction step. The question continues:      and, if $x &lt; n$, then   $$e^x &lt; \left(1-\frac{x}{n}\right)^{-n}$$   Also, by choosing a suitable $n$, deduce that $2.5 &lt; e &lt; 2.99$.   I would like a hint to help me along if anyone can help. Thanks!
109742
I have been trying to prove this by induction on $n\in \mathbb{N}$, but this approach seemed to get me nowhere. I have a suspicion it might be necessary to express $\log{n}$ as $\int_1^n 1/x\text{ }dx$, but I could not build a rigorous argument from that.  Any help greatly appreciated!
90597
Let $a&gt;0$ be a real number, such that for all integers $n\geq 1$: $n^a \in \mathbb N$ Show that $a$ must be an integer.    It's not difficult to show this when $a$ is a rational number: $2^\frac{p}{q}$ is irrational when the fraction is in lowest terms and $q \neq 1$.  When $a$ is irrational, then for all $n\geq 1$, there exists $m_n\in \mathbb N^*$, such that: $$a = \frac{\log m_n}{\log n}; \quad \text{$m_n$ is not a power of $n$}$$  I think considering $n=2,3$ is enough to show a contradiction, but I can't seem to find it. This is what I get: $$a = \frac{\log p}{\log 2} = \frac{\log q}{\log 3}$$ $$p = 2^{\log q/\log 3} $$  I think the RHS is irrational when $q$ is not a power of $3$, but I can't prove it. The closest thing I have to a solution is . But it uses an unproven conjecture, and I was hoping for a more elementary proof.