Assume $x \in \mathbb{R}$ and $(x + \frac{1}{x}) \in \mathbb{Z}$.   Use Induction to prove that for all $n \in \mathbb{N},~ (x^n + \frac{1}{x^n}) \in \mathbb{Z}$.  I'm not sure how to use the information given to prove the induction step. What I have so far is.  $P(n) : (x^n + \frac{1}{x^n}) \in \mathbb{Z}$  Base Case Then $(x^0 + \frac{1}{x^0}) = 2 \in \mathbb{Z}$  Induction Hypothesis: $x^k + \frac{1}{x^k}\in \mathbb{Z}$  Want to prove: $x^{k+1} + \frac{1}{x^{k+1}} \in \mathbb{Z}$  My first step was  $x^{k+1} + \frac{1}{x^{k+1}} = x \cdot x^k + \frac{1}{x} \cdot \frac{1}{x^k}$
47462
Assume that $x+\frac{1}{x} \in \mathbb{N}$. Prove by induction that $$x^2+\frac1{x^2}, x^3+\frac1{x^3}, \dots , x^n+\frac1{x^n}$$ is also a member of $\mathbb{N}$.  I have my base, it is indeed true for $n=1$..  I can assume it is true for $x^k+x^{-k}$ and then proove it is true for $x^{k+1}+x^{-(k+1)}$ but I'm stuck there.
115268
Prove by induction: $$\sum_{k=1}^{n} \binom n k = 2^n -1 $$ for all $n\in \mathbb{N}$.   Today I wrote calculus exam, I had this problem given.  I have the feeling that I will get $0$ points for my solution, because I did this:   Base Case: $n=1$ $$\sum_{k=1}^{1} \binom 1 1 = 1 =  2^1 -1 .$$  Induction Hypothesis: for all $n \in \mathbb{N}$: $$\sum_{k=1}^{n} \binom n k = 2^n -1 $$  Induction Step: $n \rightarrow n+1$ $$\sum_{k=1}^{n+1} \binom {n+1} {k} = \sum_{k=1}^{n} \binom {n+1} {k} + \binom{n+1}{n+1} = 2^{n+1} -1$$  Please show me my mistake because next time is my last chance in this class.
39985
Prove by induction:   $$\sum_{i=1}^{n} i \cdot 2^i = (n-1) \cdot 2^{n+1} +2$$   Basis: let $p(n)$ be the predicate.  Let $n=1$ this gives $(1-1) \cdot 2^1+1+2 = 2$ and $1 \cdot 2^1 = 2$ so its true for $p(1)$  Induction: assume $n=k$ thus $$\sum_{i=1}^{k} i \cdot 2^i = (k-1) \cdot 2^{k+1} +2$$  when $n=k+1$:  $$\sum_{i=1}^{k+1} i \cdot 2^i = \sum_{i=1}^{k} i \cdot 2^i + ((k+1)-1) \cdot 2^{(k+1)+1} +2$$  $$ =(k-1) \cdot 2^{k+1} +2 + ((k+1)-1) \cdot 2^{k+2} +2$$  $$= 2^{k+1}k - 2^{k+1} +2 +2^{k+2}(k+1) - 2^{k+2}+2$$  $$=\frac{2^{k+1}k-2^{k+1}+2 \cdot 2^{k+1}(k+1)-2 \cdot 2^{k+1} +4}{2}$$  $$=2^{k+1}k-2^{k+1}+2^{k+1}(k+1)-2^{k+1}+2$$  $$= (k-1) \cdot 2^{k+1}+((k+1)-1) \cdot 2^{k+1} +2$$  I've been messing around with the arithmetic part of this for a while now and it's getting frustrating, I'm thinking that I've possibly made a mistake at the beginning of the induction step and that's why I cant get this to work, or maybe I'm just missing something in the algebra, either way can someone please help.
37322
Prove using induction that $\forall n\in\mathbb N, \forall x\in \mathbb R: 0&lt;x&lt;1: (1-x)^n&lt;\frac 1 {1+nx}$   My attempt:   Base: for $n=1: 1-x&lt;\frac 1 {1+x}\iff 1-x^2&lt;1$, true since $0&lt;x&lt;1$.  Suppose the statement is true for $n$, prove for $n+1$:  $(1-x)^{n+1}=(1-x)(1-x)^{n}\overset{i.h}&lt;\frac{(1-x)}{1+nx}$  Now I got stuck, maybe another induction to show that $1+nx+x&lt;1+nx$? Is there another way?  Moreover, I was told it's wrong to begin with $(1-x)^{n+1}$ and reach to $\frac 1 {1+(n+1)x}$ but why? Is it assuming what I need to prove?
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?
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 ?
115524
The problem is following, prove that:  $$(a+1)(a+2)...(a+b)\text{ is divisible by } b!\text{ for every positive integer a,b}$$    I've tried solving this problem using mathematical induction, but I don't think that i did it correctly. Here's what i've done  $1.\ b=1\ (Basis)$  $$b!| (a+1)(a+2)...(a+b)$$ $$1 | a+1 \text{, which is true}$$  $2.\ b=k\ (Induction\ Hypothesis)$  $$k! | (a+1)(a+2)...(a+k)\text{, we assume it's true}$$ $$k!*n = (a+1)(a+2)...(a+k)\text{, n is some positive integer}$$  $3.\ b=k+1\ (Inductive\ Step)$  In order to prove I should get:  $$(k+1)!*m = (a+1)(a+2)...(a+k)(a+k+1)\text{, where m is some positive integer}$$ $$(a+1)(a+2)...(a+k)(a+k+1) = k!*n*(a+k+1)$$ $$(a+1)(a+2)...(a+k)(a+k+1) = (k+1)!*n + k!*n*a$$ $$(a+1)(a+2)...(a+k)(a+k+1) - a(a+1)(a+2)...(a+k) = (k+1)!*n$$ $$(a+1)(a+2)...(a+k)(k+1) = (k+1)!*n$$  And as you can see I'm returning at the beginning.  Also I've tried to use the fact that in b consecutive numbers, there must be at least one that divides b, but since i eliminate that number (because I couldn't be sure that the quotient is divisible with (b-1) or (b-2) or ... or 2. And after this i can't continue with (b-1) using this method, because it's not necessary for the other (b-1) to be consecutive.
68740
This one should be pretty easy as its only a first year math problem. it s proof by induction that Im having trouble with.  $$let\;x_{1}=1; for\;each\;n\in \mathbb{N}\;let\;x_{n+1}=\frac{2}{3}x_{n}+1; prove\; x_{n}&lt; 3\;for\;all\;n$$  If anyone is willing to spell it out really obviously step by step and explain how they got from one step to the next I would appreciate it a lot. 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!
4780
Prove by induction that $\sum\limits_{i=1}^n \frac{1}{n+i} \leq \frac{3}{4}$.   I have to prove this inequality using induction, I proved it for $n=1$ and now I have to prove it for $n+1$ assuming $n$ as hypothesis, but this seems impossible to me because the difference between the sum of $n$ and the sum of $n+1$ is a positive value. Adding a positive value on both sides of the inequality, I don't know how to prove that is always less than or equal to $\frac{3}{4}$.
6222
I'm working on a double induction problem with the following prompt:     Prove by induction on $n$ that for any real number $q &gt; 1$ and integer $n \ge 0$:   $$ 1 + q + q^2 + q^3 + \cdots + q^{n-1} + q^n = \frac {q^{n+1}-1}{q-1} $$    Based on , I would imagine the solution is:   Base case $(q,n)$ as $(2,n)$ and $(q,0)$ Assume premise for $(2,n)$ and prove $n+1$ Assume premise for $(q,0)$ and prove $q+1$   But even the base cases confuse me...for example on $(q,0)$: $$1+q^0 = \frac {q^{0+1}-1}{q-1} $$ $$2 = 1 $$  That can't right. Maybe I omit the $q^0$ on the LHS, but why?
63872
I am currently working on this problem from Hardy's Course of Pure Mathematics and have gotten stuck near the end. I was wondering if someone could help me determine what to go next.  Question  If $a_1, a_2, ...,a_n$ are all positive and $S_n=a_1+a_2+...+a_n$ then:  $(1+a_1)(1+a_2)...(1+a_n) \le 1 + S_n + \dfrac{(S_n)^2}{2!} + ... + \dfrac{(S_n)^n}{n!}$  My Attempt  Proof by induction:  I had first shown that it was true for $n=1$ and $n=2$.  Now suppose that it is true for n. Then it must also be true for $n+1$  $(1+a_1)(1+a_2)...(1+a_n)(1+a_{n+1}) \le 1 + S_n + \dfrac{(S_n)^2}{2!} + ... + \dfrac{(S_n)^n}{n!} + \dfrac{(S_{n})^{n+1}}{(n+1)!}$  Define: $(1+a_1)(1+a_2)...(1+a_n)=x$ and $1 + S_n + \dfrac{(S_n)^2}{2!} + ... + \dfrac{(S_n)^n}{n!}=y$  Then: $x+xa_{n+1} \le y+\dfrac{(S_{n})^{n+1}}{(n+1)!}$  By the induction assumption, we know that $x \le y$.  What I can't figure out  From this point, what I think the next natural step would be is to show that  $xa_{n+1} \le \dfrac{(S_{n})^{n+1}}{(n+1)!}$  I know this rearranges to:  $xa_{n+1} \le \dfrac{(S_{n})^{n}}{n!} \times \dfrac{S_n}{(n+1)} $  And feel there may be something I can do here, but haven't been able to figure anything out.
5951
I am currently studying proving by induction but I am faced with a problem.  I need to solve by induction the following question.  $$1+2+3+\ldots+n=\frac{1}{2}n(n+1)$$      for all $n &gt; 1$.  Any help on how to solve this would be appreciated.    This is what I have done so far.  Show truth for $N = 1$   Left Hand Side = 1  Right Hand Side = $\frac{1}{2} (1) (1+1) = 1$  Suppose truth for $N = k$  $$1 + 2 + 3 + ... + k = \frac{1}{2} k(k+1)$$  Proof that the equation is true for $N = k + 1$  $$1 + 2 + 3 + ... + k + (k + 1)$$  Which is Equal To  $$\frac{1}{2} k (k + 1) + (k + 1)$$  This is where I'm stuck, I don't know what else to do. The answer should be:  $$\frac{1}{2} (k+1) (k+1+1)$$  Which is equal to:  $$\frac{1}{2} (k+1) (k+2)$$  Right?  By the way sorry about the formatting, I'm still new.
105499
Use induction to prove that $2^n$ divides $(2n)!$ for any $n\in\mathbb{Z}_{\geq0}.$  How would you do the inductive step for this proof? I have the base case done.
99260
So I see that the process for proof by induction is the following (using the following statement for sake of example:  $P(n)$ is the formula for the sum of natural numbers $\leq n$:  $0 + 1 + \cdots +n = (n(n+1))/2$ )   Show that the base case is trivially true: $P(0)$: let $n = 0$. Then $0 = (0(0+1))/2$, which is true. Show that if $P(k)$ holds then $P(k+1)$ also holds. Assume $P(k)$ holds for some unspecified value of $k$. It must be then shown that $P(k+1)$ holds.   This is the part I don't get: 'Assume $P(k)$ holds'  We are just assuming something is true and then 'proving' that something else is true based on that assumption. But we never proved the assumption itself is true so it doesnt seem to hold up to me. Oviously proof by induction works so am I viewing the process incorrectly?
111412
Hi I have to show by induction over the number $n$  the following product rule and I have no idea about it. Could someone provide me the proof and a nice explaination:  $$(f\cdot g)^{(n)} (x)= \sum_{k=0}^n\tbinom n k f^{(n-k)} (x) g^{(k)} (x)$$  The $h^{(k)}$ is the $k`th$ derivative of the function $h^{(0)} := h$  I have to use the in my induction proof rhe recursion formula (Pascal Triangle)  $\tbinom n k = \tbinom {n-1} k + \tbinom {n-1} {k-1}$  with $n&gt;k&gt;0$
16144
I am trying to prove the summation formula using induction:  $$\sum_{k=1}^n \frac{1}{k(k+1)} = 1-\frac{1}{n+1}$$  So far I have...  Base case:   Let n=1 and test   $\frac{1}{k(k+1)} = 1-\frac{1}{n+1}$  $\frac{1}{1(1+1)} = 1-\frac{1}{1+1}$    $\frac{1}{2} = \frac{1}{2}$   True for n=1   Induction Hypothesis:   Assume the statement is true for the n-th case   $\sum_{k=1}^n  \frac{1}{k(k+1)} = 1-\frac{1}{n+1}$  Inductive Step:   Prove, using the Inductive Hypothesis as a premise, that   $$\sum_{k=1}^{n+1}  \frac{1}{k(k+1)} = \sum_{k=1}^{n}  \frac{1}{k(k+1)} + \frac{1}{(n+1)(n+2)} = 1-\frac1{n+1} + \frac{1}{(n+1)(n+2)} = \frac{(n+1)(n+2)}{(n+1)(n+2)}+\frac{-2-n}{(n+1)(n+2)}+\frac{1}{(n+1)(n+2)} = \frac{(n+1)(n+2)-2-n+1)}{(n+1)(n+2)} = \frac{(n+1)(n+2)-n-1}{(n+1)(n+2)} = \frac{n^2+2n+1}{(n+1)(n+2)} = \frac{(n+1)(n+1)}{(n+1)(n+2)} = \frac{n+1}{n+2}$$  To prove $$ 1-\frac{1}{n+2} = \frac{n+1}{n+2} $$ Multiply both sides by $n+2$ to get an equivalent expression. $$ (1-\frac{1}{n+2}) * (n+2) = (\frac{n+1}{n+2}) * (n+2)  $$ $$ n+1=n+2−1 $$  Does this all make sense? How can this be improved upon?