I would like to prove the following statement $$x^n-a^n=(x-a)\sum^{n-1}_{k=0}x^ka^{n-k-1},\qquad\forall n\in\Bbb N_0$$ I can easily prove it by induction using polynomial long division or series expansion however I am unsure whether or not these are "rigorous enough". I have thought about this for a while but is there a way to prove this statement in a more rigorous way? I think that the use of ellipses and "do this for the remaining $n$" gives me this uncertainty. Therefore I pose my question as follows:     Is there a rigorous way to prove this statement, or is the use of ellipses rigorous enough?   Thank you.
28543
This question is from [Number Theory George E. Andrews 1-1 #3].     Prove that $$x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+\ldots+xy^{n-2}+y^{n-1}).$$   This problem is driving me crazy. $$x^n-y^n = (x-y)(x^{n-1}+x^{n-2}y+\dots +xy^{n-2}+y^{n-1)}$$  $(x^n-y^n)/(x-y) =$ the sum for the first $n$ numbers and then I added $(xy^{(n+1)-2}+y^{(n+1)-1})$ which should equal $(x^{n+1}-y^{n+1})/(x-y)$ but I can't figure it out    This is a similar problem in the book and I tried this method but it wasn't working out      $\quad$Thereom $\bf1$-$\bf2$: $\,\,\,\,$ If $\,x$ is any real number other than $1$, then $$\sum_{j=0}^{n-1}x^j=1+x+x^2+\ldots+x^{n-1}=\dfrac{x^n-1}{x-1}.$$    $\quad$Remark: $\displaystyle\sum_{j=0}^{n-1}A_j$ is shorthand for $A_0+A_1+A_2+\ldots+A_{n-1}.$     $\quad$Proof: Again we proceed by mathematical induction. If $n=1$ then $\displaystyle\sum_{j=0}^{1-1}x^j=x^0=1$ and $(x-1)/(x-1)=1$. Thus the theorem is true for $n=1$.  $\quad$ Assuming that $\displaystyle\sum_{j=0}^{k-1}x^j=(x^k-1)/(x-1)$, we find that $$ \eqalign{ \sum^{(k+1)-1}_ {j=0}x^j &amp; = \sum^{k-1}_ {j=0}x^j+x^k=\dfrac{x^k-1}{x-1}+x^k \\ &amp;= \dfrac{x^k-1+x^{k+1}-x^k}{x-1}\\ &amp;= \dfrac{x^{k+1}-1}{x-1}. }$$   Hence condition $(\rm ii)$ is fulfilled, and we have established the theorem.    $\quad$Corollary $\bf1$-$\bf1$: $\,\,$ If $\,m$ and $n$ are positive integers and if $m&gt;1$, then $n&lt;m^n.$
78732
Prove by mathematical induction that:  $$\forall n \in \mathbb{N} : \sum_{k=1}^{2n} \frac{(-1)^{k+1}}{k} = \sum_{k=n+1}^{2n} \frac{1}{k} $$  Step 1: Show that the statement is true for $n = 1$:  LHS = $$\frac{(-1)^{1+1}}{1} = 1$$  RHS = $$\frac{1}{1} = 1$$  Step 2: Show that "if true for n = p, then true for n = p + 1":  Starting with the LHS of equality for $n = p + 1$ and try to get to the RHS by using the equality for $n = p$. Simplifying:  $$\sum_{k=1}^{2(p+1)} \frac{(-1)^{k+1}}{k} = \sum_{k=1}^{2p+2} \frac{(-1)^{k+1}}{k}$$  Breaking out the first two term:  $$ \sum_{k=1}^{2p+2} \frac{(-1)^{k+1}}{k} = \frac{(-1)^{2p+3}}{2p+2} + \frac{(-1)^{2p+2}}{2p+1} + \sum_{k=1}^{2p} \frac{(-1)^{k+1}}{k} $$  The last term can now be exchanged for the RHS in the original equality:  $$\frac{(-1)^{2p+3}}{2p+2} + \frac{(-1)^{2p+2}}{2p+1} + \sum_{k=1}^{2p} \frac{(-1)^{k+1}}{k} = \frac{(-1)^{2p+3}}{2p+2} + \frac{(-1)^{2p+2}}{2p+1} + \sum_{k=p+1}^{2p} \frac{1}{k}$$  Since $2p+3$ is odd and $2p+2$ is even, we get:  $$\frac{(-1)}{2p+2} + \frac{1}{2p+1} + \sum_{k=p+1}^{2p} \frac{1}{k} = \frac{(-1)}{2p+2} + \sum_{k=p+1}^{2p+1} \frac{1}{k}$$  ...because we can easily absorb the second term in the third term sum. However, I am stuck here because the first term is negative. I probably made a trivial error somewhere, but I am unable to find it. Any suggestions?
12773
Use mathematical induction to prove this. Here is my answer but I stuck at certain point.   Base Case:           n=1  $$(1+x)^1 \ge 1+x $$ True ,   Induction Case:           n=k assume    $$(1+x)^k \ge 1+kx $$           n=k+1           $$ (1+x)^k+1 \ge 1+(k+1)x $$           $$(1+x)^k *(1+x) \ge 1+ kx+ x $$        Stuck!!!
62003
Right, this is an exercise in Apostol, which I am not being able to solve. I was able to prove this result for a small case, that is the case when $n=2$, $[x] + \Bigl[x + \frac{1}{2}\Bigr]=[2x]$, but I am struggling with the generalization.  Prove that $$\sum\limits_{k=0}^{n-1} \Biggl[x + \frac{k}{n}\Biggr] = [nx],$$ where $[ \ ]$ denotes the greatest integer function.  Can this be proved via induction, I ask this because I have shown it to be already true for $n=2$.
87769
Given the following identity: $$\sum_{i=0}^k (-1)^i \binom ni = (-1)^k \binom {n-1}{k}.$$  This is provable by induction. However, I wonder if there is a way to prove this in a combinatorial fashion (something like subsets, groups, choosing $n$ balls from a box with $k$ balls, et cetera.)  Thank you.
5506
I encountered the following induction proof on a practice exam for calculus:  $$\sum_{k=1}^nk^2 = \frac{n(n+1)(2n+1)}{6}$$  I have to prove this statement with induction.  Can anyone please help me with this proof?
88370
Prove that if $p$ is a polynomial of degree at most $n-1$, then   $$\sum_{k=0}^n \binom{n}{k}(-1)^k p(k) = 0.$$  This was probably asked before but I couldn't find it anywhere. Can anyone please help me out here? Looks like the proof is extensive.
68681
This is motivated by my answer to .     gives the following identity:   $$ \sum_{k=1}^nH_k=(n+1)H_n-n $$  Why is this?    Note that I don't just want a proof of this fact (It's very easily done by induction, for example).  Instead, I want to know if anyone's got a really nice interpretation of this result: a very simple way to show not just that this relation is true, but why it is true.    Has anyone got a way of showing that this identity is not just true, but obvious?
88069
Based on the binomial expansion of $(1+x)^n$, show that: $$\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{n + k}{k} = (-1)^n.$$  This is a question from a very old high school exam paper I came across. It looks like it involes the product of two binomial expansions but I cannot figure this out. Any help much appreciated.
29081
I want to prove by induction that $a^n \mid b^n$ implies that $a \mid b$ holds for all integers $n\geq 1$.  Clearly for $n=1$ this is true, since if $a \mid b$, then $a \mid b$.  Suppose this is true for some $n = k$. Then $a^k \mid b^k$, so $a|b$.  $a^k \mid b^k$ means there exists some integer $m$ such that $b^k = ma^k$, and $a \mid b$ means there exists an integer $r$ such that $b=ra$.  Then we can multiply both sides of the above equality by any constant, namely $b$.   Then $b \cdot b^k = bma^k$  so $b^{k+1} = (ra)ma^k = rma^{k+1}$  which means that $a^{k+1} \mid b^{k+1}$ completing the induction step, and thus proving that for all integers $n \geq1$ the original statement holds.  Are there any logical holes in the proof?
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.
96609
I am not sure whether this is right. Can anyone verify, whether this proof is valid? Thanks!        Define a sequence $\{a_n\}_{n\ge0}$ as follows:   $$a_0=1,\qquad,a_1=3,\qquad,a_2=9,\qquad,a_n=a_{n-1}+a_{n-2}+a_{n-3}\text{ for }n\ge3.$$   Prove that for any positive integer $n$, $a_n\le3^n$.        Proof. Let $P(n)$: $a_n\le 3^n$, $n$ is a non-negative integer.      (i) Base case:         Consider when $n=0$. LHS$=a_0=1$, RHS=$3^0=1$ $\therefore$ LHS$\le$RHS, then $P(0)$ holds.   Consider when $n=1$. LHS$=a_1=3$, RHS=$3^1=3$ $\therefore$ LHS$\le$RHS, then $P(1)$ holds.   Consider when $n=1$. LHS$=a_2=9$, RHS=$3^2=9$ $\therefore$ LHS$\le$RHS, then $P(2)$ holds.         (ii) Inductive case:   Assume $P(i)$ is true for $0 \le i \le k$, $k\ge2$.      (iii) Inductive conclusion: Consider $n=k+1$.   $$ \begin{align*} \mathrm{LHS}=a_{k+1}&amp;=a_k+a_{k-1}+a_{k-2} \qquad\text{(by definition, since $k\ge 2$)}\\                     &amp;\le 3^k+3^{k-1}+3^{k-2} \qquad\text{(by Induction Hypothesis)}\\                     &amp;=3^k(3^{-1}+3^{-2}+3^{-3})\\                     &amp;=3^k\left(\frac13+\frac19+\frac1{27}\right)\\                     &amp;=\frac{13}{27} 3^k\\                     &amp;\le 3^{k+1} = \mathrm{RHS} \end{align*} $$   Therefore, by the Principle of Strong Induction, $P(n)$ is true for all non-negative positive integers $n$.
87097
So the way I think I should approach this is by getting a result for $n=1,2,3...$  and then examine them. I could easily get the Taylor series expansion for $n=1$, but then I don't really know how to proceed, because I can't always break down a power of a polynomial. And a power of a summation doesn't seem as a legit answer either.   Can anyone help? Thanks
49962
I need to prove that $$ 2^n &gt; n^3\quad \forall n\in \mathbb N, \;n&gt;9.$$  Now that is actually very easy if we prove it for real numbers using calculus. But I need a proof that uses mathematical induction.   I tried the problem for a long time, but got stuck at one step - I have to prove that:     $$ k^3 &gt; 3k^2 + 3k + 1 $$   Hints???
120645
I tried proving it but I'm quite skeptical about it:  $(\Rightarrow )$ Assume $x&lt;y$. Clearly, the base case for the induction is done. Assume $x^k&lt;y^k$ for some $k\in \mathbb{N}$.  Now, $x^{k+1}=x^k\cdot x&lt;y^k\cdot y=y^{k+1}$.   $(\Leftarrow )$ Assume for contradiction that $x\not&lt; y$. Then $y\le x$. Now, suppose $y\ne x$. Then $y&lt;x$. It follows that $y^n&lt;x^n$ for every $n\in \mathbb{N}$ from $(\Rightarrow )$. This contradicts our hypothesis. Also, if $y\not&lt; x$ then $x=y$. Then $y^n=x^n$ for every $n\in \mathbb{N}$ which also contradicts our hypothesis.  Is this proof correct?
45704
Is there an intuitive way, though I am not sure how to find a conceptual proof either, to establish the following identity: $$\sum_{k=1}^{n} \binom{n}{k} k^{k-1} (n-k)^{n-k} = n^n$$ for all natural numbers.  I am thinking about binomial formula $$\sum_{k=0}^n\binom nk x^{n-k}y^k=(x+y)^n$$ but I'm not sure how to use it.  I find this problem tantalizing because it looks as if there should be some sort of intuitive way so that is why I share it here. I am looking for an answer like  if possible. Can you find one?
62968
In algebra &amp; polynomials, how do we prove that $$x-1 \mid x^n -1?$$