Results 1 to 10 of 10

Math Help - Stuck with proof homework!

  1. #1
    Newbie
    Joined
    May 2008
    Posts
    7

    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}+{{<br />
\it nx}}^{n+2}}{ \left( 1-x \right) ^{2}}}<br />
      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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by discretemather View Post
    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}+{{<br />
\it nx}}^{n+2}}{ \left( 1-x \right) ^{2}}}<br />
      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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Apr 2008
    Posts
    1,092
    Quote Originally Posted by discretemather View Post
    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}+{{<br />
\it nx}}^{n+2}}{ \left( 1-x \right) ^{2}}}<br />
      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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    May 2008
    Posts
    7
    Quote Originally Posted by icemanfan View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by discretemather View Post
    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}+{{<br />
\it nx}}^{n+2}}{ \left( 1-x \right) ^{2}}}<br />
      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}
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by discretemather View Post

    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.

    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    May 2008
    Posts
    23
    Quote Originally Posted by Isomorphism View Post
    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
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by SaxyTimmy View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    May 2008
    Posts
    23
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: March 30th 2011, 09:50 PM
  2. [SOLVED] Mechanics Review Homework - Stuck =[
    Posted in the Math Topics Forum
    Replies: 4
    Last Post: March 12th 2009, 07:02 AM
  3. Prepositional Homework Stuck
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: December 10th 2008, 06:05 PM
  4. Functions--> homework , absolutly stuck :S
    Posted in the Math Topics Forum
    Replies: 7
    Last Post: April 11th 2008, 06:06 PM
  5. random homework quesstion, i am stuck
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: April 14th 2006, 09:25 AM

Search Tags


/mathhelpforum @mathhelpforum