Prove by induction that $2^n\le (n+1)!$ for all $n\in\Bbb N$.  What I've done so far is prove for $n=1$: $$2^1 \le (1+1)!,$$ $$2 \le 2,$$ which is correct Then I tried to prove for $n+1$, in other words, I want to get here: $$2^{n+1}\le(n+2)!.$$ So, I multiplied everything with $2$: $$2\cdot 2^n \le2\cdot (n+1)!,$$ $$2^{n+1} \le2(n+1)n!.$$ So I already have what I wanted in the left part of the inequality, but I'm stuck for the right part. Can someone help me? Thanks!
115045
I need help with this exercise. What I've done so far is prove the exercise when $n=1$. So:  $$n=1$$ $$1!\ge2^{(1-1)}$$ $$1\ge2^0$$ $$1\ge1$$ Which is true  Therefore, now that I assume that the assumption is correct, I want to prove that with $n+1$, it will also be true. So, what I've done now is:  $$P(n) \implies P(n+1) $$ $$n!+n+1\ge 2^{(n-1)}...$$ And my  problem is that I do not know how to add the $n+1$ in the right side of the equation, therefore I'm not been able to finish the exercise.  Thank you so much for your help. If something's not very clear, please let me know. I'll try to be clearer next time :)
67186
I have to do proof of $(a+b)^n$ and $(a+b)^{n+1}$ with mathematical induction.  I finished the first one $(a+b)^n = a^n + na^{n-1}b+\dots+b^n$.  I however have trouble with the second one, I don't know what to start exactly. Any help/hints?
104836
I have to prove the following inequality:     $$\forall n,m \in \mathbb{N},i\in\mathbb{N_0}:n&lt;m \implies \frac1{n^i}\binom{n}i \leq\frac1{m^i}\binom{m}i $$   I used this fact to prove an other inequality, without proving this one first, but now I am stuck. Is induction the way to do this?
62299
I have to show $n! \leq \left( \frac{n+1}{2} \right)^n$ via induction.  This is where I am stuck:  $$\left( \frac{n+2}{2} \right)^{n+1}  \geq \dots \geq =2  \left( \frac{n+1}{2} \right)^{n+1} = \left( \frac{n+1}{2} \right)^n(n+1) \geq n!(n+1) = (n+1)! $$  I approached this from both sides and this is the closest I can get. I realize that $n+2$ on the left has to be bigger than $n+1$ on the right, but I do not know who to show that it overpowers the factor two I have from the right.  What could I do to fill the dots? Currently, I just have it without the dots, but I would be happier if I could back it up.
66163
I ran across this problem in some old notes, and I frustratingly can't figure out how to do it   Let $a_i$ and $b_i$ be sequences of natural numbers, use induction to show  $\sum_{i=1}^n (a_ib_i)^{1/2} \le (\sum_{i=1}^n a_i)^{1/2}(\sum_{i=1}^n b_i)^{1/2} $  Obviously this is trivial to show for n=1. I can't make much progress on n+1. I've tried various tactics, squaring both sides etc.   Any hint or help would be appreciated. Thanks.
121674
Prove that $2n-3\leq 2^{n-2}$ , for all $n \geq 5$ by mathematical induction  I have to prove by mathematical induction that: $2n-3\leq 2^{n-2}$ , for all $n \geq 5$  Thank you for the Review.
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? ...
13650
I don't know how to explain or how to prove the following statement  If $n=ab$ and $a,b \in \mathbb{N}$ then $2^a-1 \mid 2^n-1$.  Any ideas? Perhaps an induction?  Thanks in advance.
40652
Possible Duplicate:          Prove by induction that $n!&gt;2^n$ for all integers $n\ge4$.  I know that I have to start from the basic step, which is to confirm the above for $n=4$, being $4!&gt;2^4$, which equals to $24&gt;16$.  How do I continue though. I do not know how to develop the next step.  Thank you.
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.
3416
Can you help me to prove that $$(x+y)^n\leq 2^{n-1}(x^n+y^n)$$ for $n\ge1$ and $x,y\ge0$.  I tried by induction, but I didn't get a result.
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.
88351
I would like to prove the following inequality, for $n=0,1,2,...$,   $$ \binom{2n}{n}\leq 4^n.$$ I already proved it by induction, and I'm looking for another proof.
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.
54690
I have been assigned this problem for homework:     Show that, if $a &lt; b + \epsilon$ for every  $\epsilon \gt 0$, then $a\le b$.   I have tried to go about this using Induction, but I don't know what the base case would be. It is obvious to me in my mind, but I don't know how to put it into mathematical terms on paper. any hints?
8473
Problem  For what natural numbers is $n^3 &lt; 2^n$?  Attempt @ Solution   For $n=1$, $1 &lt; 2$ Suppose $n^3 &lt; 2^n$ for some $n = k \ge 1$ It looks like the inequality is true for $n = 0$, $n = 1$ and $n\ge10$ But, how can I prove this through induction?
115678
I'm trying to apply an induction proof to show that $((n+1) 2^n - 1 $ is the sum of $(i 2^{i-1})$ from $0$ to $n$.   the base case: L.H.S = R.H.S we assume that $(k+1) 2^k - 1 $ is true. we need to prove that $(k+2) 2^{k+1} - 1$   My try to prove 3 is as follows:  $(k+2) 2^{k+1} - 1$  $(k+2) (2^k * 2) - 1$ , from 2: $2^k = 1/(k+1)$  $(k+2) (2 / (k+1)) - 1$  $(k+1) 2 - 1$  My question is, how could I get to $2^k$ from the last line to prove this formula is right?