Results 1 to 4 of 4

Math Help - Prove by Induction

  1. #1
    Member
    Joined
    Oct 2007
    Posts
    145

    Prove by Induction

    \sum_{n=0}^\infty {{n+k} \choose k}\ x^n = {1 \over {(1-x})^{k+1}}

    where |x| < 1

    Can anyone lead me here? Such questions get the better of me all the time. How should I go about improving?
    Much appreciated.
    Last edited by chopet; October 11th 2007 at 10:56 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Oct 2007
    Posts
    145
    Let K = 0.
    LHS = 1 + x + x^2 + x^3 + ....= {1 \over {1 - x}}= RHS

    using the summation of geometric progression {a \over {1 - r}}

    For K = 2,
    LHS = {2 \choose 2} x^0 + {3 \choose 2} x^1 + {4 \choose 2} x^2 + ... \ \ \ = \ 1 + 3x + 6x^2 + 10x^3 + ...

    Now I cannot use the geometric progression, and hence I come unstuck.

    For RHS,
    its {1 \over {1 - 3x + 3x^2 - x^3}} = {1 \over {{\sum_{k=0}^3} {3 \choose k} (-x)^k}}

    using Binomial Theorem
    Last edited by chopet; October 11th 2007 at 11:10 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,857
    Thanks
    321
    Awards
    1
    Quote Originally Posted by chopet View Post
    \sum_{n=0}^\infty {{n+k} \choose k}\ x^n = {1 \over {(1-x})^{k+1}}

    where |x| < 1

    Can anyone lead me here? Such questions get the better of me all the time. How should I go about improving?
    Much appreciated.
    I don't have the time right now, but to me it looks like a job for an induction proof.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Use generating functions,
    \frac{1}{1-x} = 1+x+x^2+x^3+...
    So,
    \frac{1}{(1-x)^{k+1}} = \frac{1}{1-x}\cdot ... \cdot \frac{1}{1-x}.
    Which becomes,
    (1+x+x^2+...)(1+x+x^2+...)...(1+x+x^2+...)
    Which is the LHS.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. prove by induction
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: October 23rd 2011, 08:43 AM
  2. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  3. Prove by induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 10th 2009, 08:11 AM
  4. PROVE BY INDUCTION
    Posted in the Algebra Forum
    Replies: 7
    Last Post: December 11th 2008, 07:43 AM
  5. Prove induction
    Posted in the Algebra Forum
    Replies: 2
    Last Post: November 23rd 2008, 07:05 AM

Search Tags


/mathhelpforum @mathhelpforum