# Thread: Stuck with proof homework!

1. ## Stuck with proof homework!

So I've been looking at these two problems for the last bit and have no idea on how to even approach them. Any help or guidance would be extremely appreciated.
1. Prove that if $x\neq 1$, then:
$x+2\,{x}^{2}+3\,{x}^{3}+{...}+{{\it nx}}^{n}={\frac {x- \left( n+1 \right) {x}^{n+1}+{{
\it nx}}^{n+2}}{ \left( 1-x \right) ^{2}}}
$

for every positive integer $n$.
2. We are playing a mound-splitting game - we start with a single mound of rocks. In each move, we pick a mound, split it into 2 mounds of arbitrary size (say, $a$ and $b$ rocks), multiply the # of rocks in the 2 mounds and write down the result ( $a*b$), and continue playing until only one rock remains in each mound. At the end, we add up all the numbers written down after the splits. Prove that if we start with $n$ rocks, then the final sum will be $n(n-1)/2$, no matter how we split the mounds or in which order we split them.
Thanks!

2. Originally Posted by discretemather
So I've been looking at these two problems for the last bit and have no idea on how to even approach them. Any help or guidance would be extremely appreciated.
1. Prove that if $x\neq 1$, then:
$x+2\,{x}^{2}+3\,{x}^{3}+{...}+{{\it nx}}^{n}={\frac {x- \left( n+1 \right) {x}^{n+1}+{{
\it nx}}^{n+2}}{ \left( 1-x \right) ^{2}}}
$

for every positive integer $n$.
1. induction is the best way to go as far as i can see. have you tried that?

2. We are playing a mound-splitting game - we start with a single mound of rocks. In each move, we pick a mound, split it into 2 mounds of arbitrary size (say, $a$ and $b$ rocks), multiply the # of rocks in the 2 mounds and write down the result ( $a*b$), and continue playing until only one rock remains in each mound. At the end, we add up all the numbers written down after the splits. Prove that if we start with $n$ rocks, then the final sum will be $n(n-1)/2$, no matter how we split the mounds or in which order we split them.Thanks!
dunno

3. Originally Posted by discretemather
So I've been looking at these two problems for the last bit and have no idea on how to even approach them. Any help or guidance would be extremely appreciated.
1. Prove that if $x\neq 1$, then:
$x+2\,{x}^{2}+3\,{x}^{3}+{...}+{{\it nx}}^{n}={\frac {x- \left( n+1 \right) {x}^{n+1}+{{
\it nx}}^{n+2}}{ \left( 1-x \right) ^{2}}}
$

for every positive integer $n$.
Thanks!
Problem 1 is just a straight induction. To prove that the induction holds, assume it is true for n and prove it is true for n+1. So for n+1 we add $(n+1)x^{n+1}$ to both sides. On the right, we need to make the addition compatible with a denominator of $(1-x)^2$, so multiply top and bottom by that factor and you have $\frac{(1-x)^2 \cdot (n+1)x^{n+1}}{(1-x)^2} =$

$\frac{(1 - 2x + x^2)(n+1)x^{n+1}}{(1-x)^2} =$

$\frac{(n+1)x^{n+1} - 2(n+1)x^{n+2} + (n+1)x^{n+3}}{(1-x)^2}$.

Now, when you add this factor on to $\frac{x - (n+1)x^{n+1} + nx^{n+2}}{(1-x)^2}$, you get a few cancellations. In the numerator we have:

$x - (n+1)x^{n+1} + nx^{n+2} + (n+1)x^{n+1} - 2(n+1)x^{n+2} + (n+1)x^{n+3}$ which, canceling like terms and combining, yields

$x - (n+2)x^{n+2} + (n+1)x^{n+3}$.

Hence, we have the result we want, and the induction is proven.

4. Originally Posted by icemanfan
Problem 1 is just a straight induction. To prove that the induction holds, assume it is true for n and prove it is true for n+1. So for n+1 we add $(n+1)x^{n+1}$ to both sides. On the right, we need to make the addition compatible with a denominator of $(1-x)^2$, so multiply top and bottom by that factor and you have $\frac{(1-x)^2 \cdot (n+1)x^{n+1}}{(1-x)^2} =$

$\frac{(1 - 2x + x^2)(n+1)x^{n+1}}{(1-x)^2} =$

$\frac{(n+1)x^{n+1} - 2(n+1)x^{n+2} + (n+1)x^{n+3}}{(1-x)^2}$.

Now, when you add this factor on to $\frac{x - (n+1)x^{n+1} + nx^{n+2}}{(1-x)^2}$, you get a few cancellations. In the numerator we have:

$x - (n+1)x^{n+1} + nx^{n+2} + (n+1)x^{n+1} - 2(n+1)x^{n+2} + (n+1)x^{n+3}$ which, canceling like terms and combining, yields

$x - (n+2)x^{n+2} + (n+1)x^{n+3}$.

Hence, we have the result we want, and the induction is proven.
But then I ask... Why is it true? Shouldn't both sides be combined to at least resemble each other? I've never really understood injunction. It is like saying, "If I add 1 to both sides, then it is true."... But how exactly is this a proof? It seems more like just stating what looks like the obvious.

5. Hello,

Let $N$ be this sum.

Consider $(1-x)N$

See here, a similar question : http://www.mathhelpforum.com/math-he...on-no-7-a.html

6. Originally Posted by discretemather
So I've been looking at these two problems for the last bit and have no idea on how to even approach them. Any help or guidance would be extremely appreciated.
1. Prove that if $x\neq 1$, then:
$x+2\,{x}^{2}+3\,{x}^{3}+{...}+{{\it nx}}^{n}={\frac {x- \left( n+1 \right) {x}^{n+1}+{{
\it nx}}^{n+2}}{ \left( 1-x \right) ^{2}}}
$

for every positive integer $n$.
Thanks!
I dont know why everyone is missing it(probably because the title is discrete math )

But calculus will make it a silly problem,
To prove $x+2\,{x}^{2}+3\,{x}^{3}+{...}+{{\it nx}}^{n}={\frac {x- \left( n+1 \right) {x}^{n+1}+{{\it nx}}^{n+2}}{ \left( 1-x \right) ^{2}}}$

$\sum_1^n n x^n = x\sum_0^{n-1} n x^{n-1} = x(\sum_0^n x^n)' = x\left(\frac{1 - x^{n+1}}{1 - x}\right)'$

$\left(\frac{1 - x^{n+1}}{1 - x}\right)' = \frac{(1-x)(-(n+1)x^n) + (1 - x^{n+1})}{(1-x)^2} = \frac{1 + nx^{n+1} - (n+1)x^n}{(1-x)^2}$

$\sum_1^n n x^n = x\left(\frac{1 - x^{n+1}}{1 - x}\right)' = \frac{x + nx^{n+2} - (n+1)x^{n+1}}{(1-x)^2}$

7. Originally Posted by discretemather

We are playing a mound-splitting game - we start with a single mound of rocks. In each move, we pick a mound, split it into 2 mounds of arbitrary size (say, $a$ and $b$ rocks), multiply the # of rocks in the 2 mounds and write down the result ( $a*b$), and continue playing until only one rock remains in each mound. At the end, we add up all the numbers written down after the splits. Prove that if we start with $n$ rocks, then the final sum will be $n(n-1)/2$, no matter how we split the mounds or in which order we split them.Thanks!
This problem is easy by strong induction. But I hope some one can give a nice little proof using some invariance or some other trick.

Let P(n) be the statement that a set n rocks which follow your process give a sum of $n(n-1)/2$.

First lets prove for n=2, 2 can break as only 1+1 and the product is 1. And so is 2(2-1)/2. Thus n=2 is proved.

Now lets say P(k) holds for all k < n, and we will prove P(n) is true.

Let n break into a and b. Now a,b < n and a+b = n.

By induction hypothesis, the sum for products by breaking 'a' completely is a(a-1)/2 and similarly for b it is b(b-1)/2. Now for n, we have broken down into a and b, so we will write ab first then we will add numbers that sum up to a(a-1)/2 and b(b-1)/2. So finally we get the sum:

$ab + \frac{a(a-1)}{2} + \frac{b(b-1)}{2} = ab + \frac{a^2+b^2}2 - \frac{a+b}2 = \frac{2ab+ a^2+b^2}2 - \frac{a+b}2$

$= \frac{2ab+ a^2+b^2}2 - \frac{a+b}2 = \frac{(a+b)^2}2 - \frac{a+b}2 = \frac{n^2 - n}2$

Thus we have proved P(n) is true.

8. Originally Posted by Isomorphism
This problem is easy by strong induction. But I hope some one can give a nice little proof using some invariance or some other trick.

No, no I unfortunately don't think that is the case. I am pretty sure they wanted him to use strong induction. :P

9. Originally Posted by SaxyTimmy
No, no I unfortunately don't think that is the case. I am pretty sure they wanted him to use strong induction. :P
Ya I know, discrete maths would probably want that. But I just wanted to see another proof. I dont like induction since it does not give too much insight into a problem.

10. Yeah, that is true enough. I personally love induction just because the idea is ingenious, and normally proofs with it are fairly simple. However, I also do appreciate seeing the tricks like you used for the first part of the question. That to me has way more insight, and ingenuity. Where with induction the proof method takes all the insight and ingenuity from the person creating the proof.