How would I go about proving that $n! \ge 2^{n-1}\ \forall n \ge 1$? The base case makes sense to me, but when I do the inductive step, I go here using the inductive step:  $$ n+ 1 = k+1 $$ $$ (k+1)! \ge 2^{(k+1)-1} $$ $$ (k+1)! = (k+1)\cdot k!$$ $$\ 2^{k-1+1} = 2^k = 2^{k-1} \cdot 2 $$ $$(k+1) \cdot k! \ge 2^{k-1} \cdot 2 $$ $$ \therefore (n+1) \cdot n! \ge 2^{n-1} \cdot 2$$  Is this a viable proof? If not, what do I need to do differently in order to make it correct? Have I not gone far enough?
837
Im trying to solve the following question         In the second step  where do they get $k!=2^k-1?$
60099
$$a_1 = 1$$  $$a_{n+1}=\frac{1}{2} \left(a_n+\frac{2}{a_n}\right) \ge \sqrt{a_n \cdot\frac{2}{a_n}} = \sqrt{2}$$  I don't understand what happens at the $\ge$ step. Are there any middle steps which can help me understand why is that so?
115600
Use induction to prove that that $8^{n} | (4n)!$ for all positive integers $n$  So far I have: Base case (n = 1) = $8^{1} | (4(1))!$  = $8 | 24$ which is true.  Induction Step:  $8^{n + 1} | (4(n + 1))!$  $8^{n + 1} | (4n + 4)!$   A bit confused as to how to close this proof out, also wanted to make sure my current progress is correct as well. Any help is appreciated.
101831
I am trying to prove that for every element of $\mathbb{N}$, that                    $2^n \leq 2^{n+1} - 2^{n-1} - 1.$ I started by showing that initial case, of $n=1$, is true. Then I proceed to the inductive step by assuming that for some $k$ in $\mathbb{N}$,                     $2^k \leq 2^{k+1} - 2^{k-1} - 1$.  Then, for $n=k+1$,                    $2^{k+1} \leq 2^{k+2} - 2^{k} - 1$. Is this sufficient to prove the statement by induction or do I have to expand the exponentials to rearrange the inequality in a different way?
70085
Problem: $2^n &gt; n^2, \forall n \in \mathbb{N} , n \geq 5$ Base: $2^5 &gt; 5^2$ Induction Hypothesis: Assume for $n = k \geq 5$ that $2^k&gt;k^2$ Inductive Step: $$2^k &gt; k^2$$ $$2^k \times  2 &gt; k^2 \times 2$$ $$2^{k+1} &gt; 2k^2$$ From there I can finish the proof by asserting that $k^2 &gt; 2k+1, \forall k \in \mathbb{N} , k \geq 3$. Do I need to prove that $k^2 &gt; 2k+1, \forall k \in \mathbb{N} , k \geq 3$. Or can I substitute it into my inequality?
71846
I would appreciate if somebody could help me with the following problem:      For a given positive integer $n$, can we find positive integers $a$ and $k$ ($k\geq 2$) such that $2^n-1=a^k$?    The answer would be no, I  guess.  Please give me some ideas!
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.
88073
I am trying to prove the following by Mathematical Induction:  $$\sum_{i=1}^n i\cdot i! = (n+1)!-1\quad\text{for all integers $n\ge 1$}$$   My proof by Induction follows: First prove $P(1)$ is true,  $$\sum_{i=1}^1 i\cdot i! = (1+1)! - 1$$  Then, for all integers $k &gt;= 1$, if $P(k)$ is true then $P(k+1)$ is also true,  $$ \sum_{i=1}^k i\cdot i! = (k+1)! - 1$$ Then, we must show that $P(k+1)$ is true   $$ \sum_{i=1}^{k+1} i\cdot i! = ((k+1)+1)! - 1\\ \sum_{i=1}^{k+1} i\cdot i! = (k+2)! - 1$$  I am currently struggling with the next step to show that $P(k)$ is equal to $P(k+1)$. How would I finish this prove by induction?
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.
48430
I want to prove with mathematical induction that:  $$\sum_{i=1}^n i \cdot i! = (n+1)! - 1$$  So in the first step we define $n = 1$:  $$\sum_{i=1}^1 i \cdot i! = 1 \cdot 1! = 1 = 2! - 1$$  In the second step we define $n = n + 1$:  $$\sum_{i=1}^{n+1} i \cdot i! = \sum_{i=1}^n i \cdot i! + (n+1)(n+1)!$$ $$\implies (n+1)! - 1 + (n+1)(n+1)!$$  This can now be simplified to $(n+2)(n+1)! - 1$ but I do not see how...  We could do $(n+1)!(-1 + (n+1)) = (n+1)! \cdot n$ but still this will not be the same as above.  What did I miss?  Bodo
64537
Prove that for every positive integer $n \ge 2$ $$\sum^n_{k=1}k \sqrt{\binom nk}\leq\sqrt{2^{n-1}n^3}$$ I tried it by induction but I didn't know how to end it.
56757
Prove if $n \in \mathbb N$, then $\frac{1}{2!}+\frac{2}{3!}+\frac{3}{4!}+\cdots+\frac{n}{\left(n+1\right)!} = 1-\frac{1}{\left(n+1\right)!}$   So I proved the base case where $n=1$ and got $\frac{1}{2}$  Then since $n=k$ implies $n=k+1$ I setup the problem like so:  $\frac{k}{(k+1)!}+\frac{(k+1)}{(k+2)!}=1-\frac{1}{(k+2)!}$  After trying to simplify it I got the following:  $\frac{k(k+2)!+(k+1)(k+1)!}{(k+1)!(k+2)!}=1-\frac{1}{(k+2)!}$  However, I'm having trouble simplifying it to match the RHS.  Hints?
107728
Is there a nice combinatorial proof of the following identity?  (That is, by showing that both sides count the same thing.) $$\sum_{k=0}^n k \cdot k! = (n+1)! -1 $$ I was searching Wikipedia for nice identities to assign to my students for a homework on combinatorial proof, and thought this one looked innocent enough, but then realized I couldn't solve it myself.  Perhaps we should take the set of permutations of $n+1$ letters and partition it in some clever way (maybe the $-1$ suggests that the identity should be set aside), but I can't see what that might be.  Of course it is very easy to prove by induction; that's not what I'm looking for.
110473
Let $g_n= {2^2}^n +1 $. Prove $g_0 · g_1 · · · g_{n−1} = g_{n} − 2$.    I'm not sure how to start this proof, if it should be done algebraically or if I should try to use a proof by induction.
1136
I'm having difficulty solving an exercise in my course.  The question is:      Prove that $n!\geq 2^n$.   We have to do this by induction. I started like this:   The lowest natural number where the assumption is correct is $4$ as: $4! \geq 2^4 \iff 24 \ge 16$. The assumption is: $n! \ge 2^n$.   Now proof for $(n+1)$ which brings me to: $(n+1)! \ge 2^{(n+1)}$  I think I can rewrite it somehow like this:  $$ {(n+1)} \times {n!}  \stackrel{\text{(definition of factorial)}}{\ge} 2^n \times 2 $$  $$ (n+1) \times 2^n \ge 2^n \times 2 $$  Then I think I can eliminate the $2^n$ and have something like this: $n+1 \ge 2$, or $n \ge 1$.  But I think I'm wrong here some where and was hoping somebody has some advice on this. How can I prove the above assumption?  Any help would be appreciated, kind regards.
87479
I'm trying to do homework problems and for the most part I've been getting the results. For this one though, I am having some trouble since its $2^n$ and I can't relate it properly:     Prove using simple induction that $n &lt; 2^n$ for all $n \ge 1$.   So obviously, the basis step holds as $1 &lt; 3$. Now, I assume that $n = k$ holds as well and have to prove for $n=k+1$. This is the step I am having trouble with as I cannot relate the induction hypothesis with what I want to end up with. Can anybody show me a model solution for this one? I think my trouble comes because of the $2^n $
6856
Here is a problem which i have not been able to do for quite sometime.   For $n \geq 2$, show that $n \nmid 2^{n}-1$.   I have thought of proving this in two ways: One by using induction which didn't actually work. Next by Fermat's little theorem we have $2^{p-1} \equiv 1 \ (\text{mod} \ p)$, which actually says that for $p \mid 2^{p}-2$. But i couldn't proceed more than this. Any ideas by which i can actually solve the problem?