I'd like to see a simple proof of $$x^n−y^n=(x−y)(x^{n−1}+x^{n−2}y+…+xy^{n−2}+y^{n−1})$$  I don't know what proof by induction is... is there a simpler way? The previous  on this doesn't really solve my problem.... I don't understand the induction proofs.  The text that I am reading with this is this:
122004
I am looking at a proof of the power rule and I see this:  $x^n - a^n = (x-a)(x^{n-1} + x^{n-2}*a + {...} + xa^{n-2} + a^{n-1})$  Where does this come from?  It's used in this proof which I'm trying to understand:    What is it called?
71134
I understand the idea of the proof. I just want to make sure I wrote my proof well.  Suppose $n$ is not prime. Then $\exists x,y \in \mathbb{Z}$ such that $n = xy$.  $2^{xy} - 1 = (2^x)^y - 1$  $ = (2^y - 1)(2^{y(x-1)} + 2^{y(x-2)} + ... + 2^{y} + 1)$  Since $2^{n} - 1$ is divisible by $2^y - 1$ it must be that $2^n - 1$ is not prime. Contradiction. Thus $n$ must be prime.  How does this look?
36022
the background I'm allowed to deal with to solve this problem is as follows:  Definition of +: \begin{equation} m+0=m\quad \text{for all}\quad m \in \mathbb{N} \\ m+(k+1) = (m+k)+1  \end{equation} in conjunction with the induction property of $\mathbb{N}$. In a previous task I showed that $ 0+m=m \quad \forall \, m \in \mathbb{N}$.  Task: Prove $m+n=n+m$ by induction on $n$.  Now, it follows directly that $0+m=m=m+0$. With the assumption that $k+m=m+k$ for a $k\in\mathbb{N}$, it can be deduced: \begin{eqnarray} m+(k+1) &amp; = &amp; (m+k)+1\quad \text{by def. of}+\\ &amp; = &amp; (k+m) + 1\quad \text{with assumption}\\ &amp; = &amp; k + (m+1)\quad \text{by def. of}+. \end{eqnarray} Here, it looks to me that the true base step would be $m+1 = 1+m$, because then it would be possible to bring the proof straight to an end. But I tried hard to hack this last nut without any results. Is there anybody who could help me with this? Or maybe there is a completely different way to come up with the proof requested?  Thanks in advance for your help
25938
$\dfrac{n}{2} \le \dfrac{1}{1}+\dfrac{1}{2}+\dfrac{1}{3}+...+\dfrac{1}{2^n - 1} \le n $  I've Tried for hours but didn't got any striking idea. I don't have any efforts to show rather than induction. Please Try If you 've non-inductive proof.
60296
I am a CS undergrad and I'm studying for the finals in college and I saw this question in an exercise list:     Prove, using mathematical induction, that $2^n &gt; n^2$ for all integer n greater than $4$   So I started:  Base case: $n = 5$ (the problem states "$n$ greater than $4$", so let's pick the first integer that matches)  $2^5 &gt; 5^2 \implies 32 &gt; 25$ - ok!  Now, Inductive Step:  $2^{n+1} &gt; (n+1)^2$  now expanding  $2 * 2^n &gt; n^2 + 2n + 1$  Well, I can't go on, I don't know how to finish this proof. Could anyone help me with this one?  Also, I know that the statement (inductive hypothesis) is true. Simply, I'll have a number to an exponent $n$ twice, next to $n$ squared and $2n$ (which could be seen as quadratic and linear functions) which "grows" much lower than the exponential one. It could be easily "proved by example" with any $n$ greater than $4$.  I want to know how to prove it algebraically , so my professor does not freak out.  thanks in advance.
8096
I am trying to prove that $n^2 \leq 2^n$ for all natural $n$ with $n \ne 3$. My steps are:    induction base case: $n=0:$ $0² \leq 2⁰$ which is okay.    inductive step: $n \rightarrow n+1:$ $(n+1)²\leq2^{n+1}$ $$(n+1)^2 = n^2 + 2n + 1 = ...help...\leq 2^{n+1}$$   I know the bernoulli inequality but don't know where to use it, if I even need to. I have problems when it comes to proving things which are based on orders..
25419
Prove by induction that $5^n - 1$ is divisible by $4$.   How should I use induction in this problem. Do you have any hints for solving this problem?  Thank you so much.
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.
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?
85343
Need guidance on this proof by mathematical induction. I am new to this type of math and don't know how exactly to get started.   $$ 1^3  +  2^3  +  3^3  +  \ldots  +  n^3  =  \left[\frac{n(n+1)}{2}\right]^2 $$
23125
I aim to show that $$(n+1)^n&lt;n^{(n+1)}$$ for all $n \geq 3$. I tried induction, but it didn't work. What should I do?
43934
How do I show via inductive proof (and without the use of the binomial theorem) that $$ {n\choose k} \in {\mathbb{N}} $$ $$\text{ for  all }\: n,k \in \mathbb{N}_0\: \text{ with }\: n≥k .$$ For my induction proof, I would show that$$  {n\choose k-1}+{n\choose k} = {n+1 \choose k}   $$ is true. However, how do I start the induction correctly with the base cases and the hypothesis? As far as I know, I cannot simply assume $$ {n\choose k-1}+{n\choose k}, $$  so how do I come to this derivation?
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.
50979
Theorem. Let $X$ denote an arbitrary set such that $|X|=n$. Then $|\mathcal P(X)|=2^n$.      Proof. The proof is by induction on the numbers of elements of $X$.      For the base case, suppose $|X|=0$. Clearly, $X=\emptyset$. But the empty set is the only subset of itself, so $|\mathcal P(X)|=1=2^0$.      Now the induction step. Suppose $|X|=n$; by the induction hypotesis, we know that $|\mathcal P(X)|=2^n$. Let $Y$ be a set with $n+1$ elements, namely $Y=X\cup\{a\}$. There are two kinds of subsets of $Y$: those that include $a$ and those that don't. The first are exactly the subsets of $X$, and there are $2^n$ of them. The latter are sets of the form $Z\cup\{a\}$, where $Z\in\mathcal P(X)$; since there are $2^n$ possible choices for $Z$, there must be exactly $2^n$ subsets of $Y$ of which $a$ is an element. Therefore $|\mathcal P(Y)|=2^n+2^n=2^{n+1}$. $\square$      From the above explanation, I don't understand why the set that contains $\{a\}$ will contain $2^{|n|}$ elements when it should clearly be $2^{|1|}$.  The construction of a new set $S$ is the union of the old set with cardinality $n$ and an new element $\{a\}$, therefore the set that do not contain $\{a\}$ still has cardinality $n$ and the set that contains $\{a\}$ is just $\{a\}$, one element...  Can someone please elucidate?
114041
I'm not entirely sure which proof method to use?  I'm stuck between induction or proof by cases.  --- edit ---  I have gotten a better understanding now, as I am using proof by cases, however it how can I prove that my answer is correct?
76251
How many different proofs are there that $a^n-b^n =(a-b)\sum_{i=0}^{n-1} a^i b^{n-1-i} $ for positive integer $n$ and real $a, b$?  You can use any techniques you want. My proof just uses algebra, summation, and induction, but if you want to use invariant sheaves over covalent topologies, that is fine.  I decided that I would try to produce a proof by induction. I find it interesting that my proof shows that if it is true for $n-1$, then it is true for $n+1$. This means that two base cases have to be proven: $n=1$ and $n=2$. Fortunately, those are easy.  I am sure that my proof is known,  but I do not recall having seen it before.  Here is the induction step:  $\begin{array}\\ a^{n+1}-b^{n+1} &amp;=a^{n+1}-a^nb+a^nb-b^{n+1}\\ &amp;=a^{n+1}-a^nb +a^nb-ab^n +ab^n-b^{n+1}\\  &amp;=(a-b)a^n +ab(a^{n-1}-b^{n-1}) +(a-b)b^n\\  &amp;=(a-b)(a^n+b^n) +ab(a^{n-1}-b^{n-1}) \\  &amp;=(a-b)(a^n+b^n) +ab((a-b)\sum_{i=0}^{n-2} a^i b^{n-2-i}) \ \  \text{(The induction hypothesis)} \\  &amp;=(a-b)(a^n+b^n+ab\sum_{i=0}^{n-2} a^i b^{n-2-i}) \\  &amp;=(a-b)(a^n+b^n+\sum_{i=0}^{n-2} a^{i+1} b^{n-1-i}) \\  &amp;=(a-b)(a^n+b^n+\sum_{i=1}^{n-1} a^{i} b^{n-i}) \\  &amp;=(a-b)\sum_{i=0}^{n} a^{i} b^{n-i} \\  \end{array} $
12205
Prove by induction: Find a, and prove the postulate by mathematical induction.  $$\text{For all}~ n &gt; a,~ n! &gt; n^3$$  Where ! refers to factorial.  So far I've done a bit of it, I'll skip right to the inductive statement and assume that $k! &gt; k^3$, then try to prove $(k+1)! &gt; (k+1)^3$  Inductive statement: $(n+1)! &gt; (n+1)^3$  $(n+1)^3= n^3 + 3n^2 + 3n + 1 &lt; n! + 3n^2 + 3n + 1$ (By Induction Hypothesis)  ...But now I'm stuck. Does anyone know where to go next?