Using induction, I have to show that $\forall n \in \mathbb{N}, n \ge 3$ the equation:  $$\dfrac{1}{x_1} + \dfrac{1}{x_2} + ... + \dfrac{1}{x_n} = 1$$  has a solution $(x_1, x_2, ..., x_n) \in (\mathbb{N^*}, \mathbb{N^*}, ... \mathbb{N^*})$ (so a solution of all non-zero natural numbers) such that  $$x_1 &lt; x_2 &lt; ... &lt; x_n$$  I don't even see how I could prove the base case. If we have:  $$p(3) : \dfrac{1}{x_1} + \dfrac{1}{x_2} + \dfrac{1}{x_3} = 1$$  I don't see the $3$ natural numbers that satisfy the equation and at the same time satisfy the condition $x_1 &lt; x_2 &lt; x_3$. So I can't even prove the base case, let alone imply $p(k + 1)$ if I assume $p(k)$ true. Even if I get the equation to a common denominator and multiply, I get:  $$x_1 x_2 + x_1x_3 + x_2 x_3 = x_1 x_2 x_3$$  So it didn't really get any more obvious. I thought that these might be the second and third Vieta's formulas for a $3$rd degree polynomial, but I don't see how I could construct a polynomial that has all $3$ of its roots natural and satisfy the condition $x_1 &lt; x_2 &lt; x_3$. Besides, the exercise clearly says that this should be proved using induction.
90457
I have a hard induction problem here that I feel completly lost on.  For every $n\ge3$ there is n different positive integer $a_1,...,a_n$ so that $\frac{1}{a_1}+\frac{1}{a_2}+...+\frac{1}{a_n}=1$.  There is only one possible solution for $n=3 $  $\frac{1}{2}+\frac{1}{3}+\frac{1}{6}=1$  for $n=4$ there is 2 possible solutions and they both start with $\frac{1}{2}$.  $\frac{1}{2}+\frac{1}{3}+\frac{1}{8}+\frac{1}{24}$ and $\frac{1}{2}+\frac{1}{4}+\frac{1}{5}+\frac{1}{20}$.  I think the first one is the one.  For $n=5$ there is alot of different possible solutions but it have to start with at least $\frac 13$  I think it have to start with $\frac 12+\frac13$ and then be some kind of sum answer for the last $\frac16$ based on $n$. But I don't know  I have tried finding a pattern but not getting anywhere anymore. Any tips on how to tackle a problem like this?
43553
The question: The terms of a sequence are given recursively as  \begin{cases} a_0 = 1,\\ a_1 = 1 \\a_n=2a_{n-1} + 3a_{n-2} \quad\text{ for } n \geq 2  \end{cases} prove by mathematical induction $a_n = \frac12(3^n) +\frac12(-1)^n$ for all $n \geq 0$  I've started by proving that the formula works e.g $$a_0= 1\implies a_0 = \frac12(3^0)+\frac12(-1)^0 = 1 \\a_1=1\implies a_1 = \frac12(3^1) + \frac12(-1)^{1} = 1$$  Therefore $p(1)$ and $p(2)$ are true  Now I have to do the hard part.. the inductive step suppose $p(1), p(2),\ldots, p(k)$, that is $a_{k+1} = 2a_{k} + 3a_{k-1}$ Im not sure where to really go from here.
98209
The equation $X^{n}  + Y^{n}  = Z^{n}$    , where $n   \geq  3$     is a natural number, has no solutions at all where $X,Y,Z$     are integers.   My solution:  False. Because if we let $X=0  ,Y=0$,  then $0^{3}+0^{3}=0^{3}$  . Thus there is a solution for the equation $X^{n}  + Y^{n}  = Z^{n}$,   where $X,Y,Z$   are integers.  Can anyone please give feedback on my answer and state whether it is correct on not.
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?
93701
Question: Prove $\forall n\geq 2,n\in\mathbb{Z}$, $(n+1)\mid(n^3+1)$    I know that it is possible to solve by factoring $n^3+1$ and showing that $n+1$ is a multiple, but I would like to show this via induction.  Attempt: Using induction:  Let $n=2:3\mid 9$, so true for $n=2$  (1) Assume true for $n=k:(k+1)\mid(k^3+1)$, so $(k+1)r=k^3+1$ for some $r\in\mathbb{Z}$  (2) Let $n=k+1:(k+2)\mid(k+1)^3+1$, so $(k+2)s=(k+1)^3+1$ for some $s\in\mathbb{Z}$  From (2) we have $(k+1)s+s=(k+1)^3+1$, subbing (1) into (2), I get $k^3+1+s=(k+1)^3+1$  Therefore $k^3+s=(k+1)^3$.  Setting $s=3k^2+3k+1$, this holds.  Where am I going wrong, is the proof valid, any help would be greatly appreciated.
111893
Let $f(x)=x^n+5x^{n-1}+3$ where $n\geq1$ is an integer. Prove that $f(x)$ can't be expressed as the product of two polynomials each of which has all its coefficients integers and degree $\geq1$.   If the condition that each polynomial must have all its coefficients integers was not there, then I needed to show only that $f(x)$ is irreducible over real numbers. But since this condition is given,therefore, we can't exclude the case when $f(x)$ is reducible over real numbers but not with polynomials of integer coefficients. Anyone with idea how to proceed? Thanks in advance!!
9458
Proove by the Complete Induction for every $n\in \mathbb{N}, n \geq 1$ $$\frac{1}{\sqrt{1}} + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} + ... + \frac{1}{\sqrt{n}} &gt; \sqrt{n}$$.  I know only the basis - $\frac{1}{\sqrt{1}} \geq \sqrt{1}$.  But, I dont know how to do the change from the regular induction to the induction of Set theroy(Complete Induction).
72759
Suppose that $a_{1}&lt;a_{2}&lt;…&lt;a_{n}$. Prove that the equation  $ \frac{1}{x-a_{1}}+\frac{1}{x-a_{2}} +…+\frac{1}{x-a_{n}}=c$ has exactly $n-1$ roots if $c=0$ and $n$ roots if $c\neq 0$.    I am absolutely not sure but I think I need to use Rolle's theorem on this. Multiply both sides by $x-a_{1}$ so we get:  $1+\frac{x-a_{1}}{x-a_{2}}+…+\frac{x-a_{1}}{x-a_{n}}-c(x-a_{1})=0$. Now it is defined for $a_{1}$ but not for $a_{2},…,a_{n}.$. If we consider the interval $(a_{1}-\varepsilon,a_{n}+\varepsilon), \varepsilon&gt;0$ we get..nowhere. I want to create an interval with endpoints that are solutions to the equation. Yet I don't know how to prove that there are exactly $n$ roots(Fundamental theorem of algebra can't be used).
81069
Use Mathematical induction to prove that for all integers, $n$ is greater than or equal to $1$. I am confused on what to do after I do the the basis step that is using $n$ as $1$.   $$\frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} +...+\frac{1}{n(n+1)}=1-\frac{1}{n+1}$$
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.
61315
Prove by induction that   $$ D_n = (n-1)(D_{n-1}+D_{n-2}), n&gt;2 $$  where $D_n$ is the number of derangements of $n$ objects.  I am a little rusty in induction, and here's what I have done so far.  Basis step:  This is easy to prove and trivial, it works for $n=3$ and this is the basis step.  Induction step: Suppose the formula holds for $n$. I will use the relation:  \begin{equation} D_n = nD_{n-1} + (-1)^n, n\ge2 \label{u28.eq.1} \tag{i} \end{equation}  which I know is true because I have proved it before. So  $$ D_{n+1} = (n+1)D_n + (-1)^{n+1} =(n+1)D_n-(-1)^n $$  I use again formula \eqref{u28.eq.1} for $(-1)^n$ and obtain  $$ (n+1)D_n-D_n+nD_{n-1} = n(D_n+D_{n-1}), $$  which is of course what I wanted to prove. The thing is that I didn't use the induction step and I think I am wrong at some step, but I cannot tell where.
60101
Let $n \in \mathbb N^+$. Show that if $x_1, x_2, ... , x_n$ are $n$ real numbers such that $-1 \le x_i \le 0$ for each $1 \le i \le n$, then $$(1 + x_1)(1 + x_2)...(1 + x_n) \ge 1 + x_1 + x_2 + ... + x_n$$  I am using a proof by induction, but I am unable to complete it. I would appreciate any tips on how I could finish the proof.   Incomplete Proof Let $P(n)$ be the proposition that $(1 + x_1)(1 + x_2)...(1 + x_n) \ge 1 + \sum_{i = 1} ^ n x_i$. When $n = 1$, LHS = RHS = $1 + x_i$. Clearly $1 + x_i \ge 1 + x_i$ and so $P(1)$ is true. Assume that $P(k)$ is true, i.e. $(1 + x_1)(1 + x_2)...(1 + x_k) \ge 1 + \sum_{i=1}^k x_i$. Case 1 Suppose $x_{k + 1}  = -1$. Then $1 + x_{k + 1} = 0$, hence LHS = $(1 + x_1)(1 + x_2)...(1 + x_k)(1 + x_{k+1}) = 0$. RHS = $1 + x_1 + x_2 + ... + x_k - 1 = x_1 + x_2 + ... + x_k$ which is always nonpositive since each $x_i$ is nonpositive. Hence RHS $\le 0$ and so LHS $\ge$ RHS. Case 2 Suppose $x_{k+1} = 0$. Then $1 + x_{k+1} = 1$, hence multiplying it to LHS does not change anything. Also, adding $x_{k+1}$ to RHS does not change anything. Therefore, LHS $\ge$ RHS still holds. Case 3 Suppose $-1 &lt; x_{k+1} &lt; 0$. Then $0 &lt; 1 + x_{k+1} &lt; 1$. Adding $x_{k+1}$ to RHS makes the RHS smaller since $x_{k+1}$ is negative. If LHS $= 0$, then multiplying $1 + x_{k+1}$ to LHS does not change anything, and so LHS $\ge$ RHS holds. If LHS > $0$, then multiplying $1 + x_{k+1}$ to LHS makes the LHS smaller since $0 &lt; 1 + x_{k+1} &lt; 1$. In this case LHS $\ge$ RHS does not necessarily hold? ...
55339
let $a,b,c \in\mathbb{R} ,a&lt;3$    and all roots $p(x)=x^3+ax^2+bx+c=0$ be negative .    then prove that $b+c\neq 4$   MyTry :   we have $x_1&lt;0 ,x_2&lt;0,x_3&lt;0$ So: $$x_1+x_2+x_3=\dfrac{-a}{1}=-a \to a\in (0,3)$$ and :  $$x_1\cdot x_2\cdot x_3=\dfrac{-c}{1}=-c$$  now what ?
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.
15822
I am trying to prove: $P(n): |x_1| + \cdots + |x_n| \leq |x_1 + \cdots +x_n|$ for all natural numbers $n$. The $x_i$ are real numbers.  Base: Let $n =1$:    we have $|x_1| \leq |x_1|$ which is clearly true  Step: Let $k$ exist in the integers such that $k \geq 1$ and assume $P(k)$ is true.  This is where I am lost. I do not see how to leverage the induction hypothesis.  Here is my latest approach:  Can you do the following in the induction step: Let $Y$ = |$x_1$ +...+$x_n$| and Let $Z$ = |$x_1$| +...+ |$x_n$| Then we have: |$Y$ + $x_n+1$| $\leq$ $Z$ + |$x_n+1$|. $Y$ $\leq$ $Z$ from the induction step, and then from the base case this is just another triangle inequality. End of proof.
91047
I'm having some trouble proving the following statement using mathematical induction:   $$\frac{1}{2}n^{\frac{3}{2}} \leq \sqrt{1} + \sqrt{2} + \sqrt{3} + \sqrt{4} + ... + \sqrt{n}      ,\text{ (for all sufficiently large n)}$$   I'm sort of confused because $n^{\frac{3}{2}}$ = $n  n^{\frac{1}{2}}$ which means that there are n of the largest possible root values on the left hand side while the right hand side has values like $\sqrt{1}$, $\sqrt{2}$, etc. As n grows sufficiently large wouldn't the left hand side outgrow the right hand side no matter what the constant multiple is? If I'm thinking about this correctly just let me know, if not, any help would be appreciated.
105302
Given $a^3 + b^{3}+ c^{3}= (a+b+c)^{3} $.  Prove that for any natural number $n$, $$a^{2n+1}+b^{2n+1}+c^{2n+1}=(a+b+c)^{2n+1}$$  I first tried mathematical induction but did not proceed anywhere. Can the formula $(a+b+c)^{3}=a^{3}+b^{3}+c^{3}+3(a+b)(b+c)(c+a)$   be directly used? Can this problem be solved using mathematical induction?