Stuck with proof homework!

Printable View

May 21st 2008, 05:37 PM
discretemather

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!
May 21st 2008, 05:50 PM
Jhevon
Quote:
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.
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?
Quote:

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 :p
May 21st 2008, 05:57 PM
icemanfan
Quote:
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.

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 to both sides. On the right, we need to make the addition compatible with a denominator of , so multiply top and bottom by that factor and you have

.

Now, when you add this factor on to , you get a few cancellations. In the numerator we have:

which, canceling like terms and combining, yields

.

Hence, we have the result we want, and the induction is proven.
May 21st 2008, 09:27 PM
discretemather

Quote:

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.
May 22nd 2008, 12:04 AM
Moo

Hello,

Let $N$ be this sum.

Consider $(1-x)N$ (Wink)

See here, a similar question : http://www.mathhelpforum.com/math-he...on-no-7-a.html
May 22nd 2008, 12:07 AM
Isomorphism
Quote:
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.
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 :p)

But calculus will make it a silly problem,
To prove
May 22nd 2008, 01:30 AM
Isomorphism

Quote:

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.

(Whew)
May 23rd 2008, 08:10 PM
SaxyTimmy

Quote:

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
May 23rd 2008, 08:13 PM
Isomorphism

Quote:

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.
May 23rd 2008, 08:22 PM
SaxyTimmy

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.