Results 1 to 6 of 6

Math Help - Identity using binomial theorem

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    8

    Identity using binomial theorem

    Hi Guys first of all I would to thank in advance all people that read/try to solve this problem.

    The problem is: prove that for all positive integer k \leq n the following equality hold.
    \sum_{i=0}^{k}\left( \begin{array}{c}n\\i\end{array}\right)\cdot (-1)^i = \left( \begin{array}{c}n-1\\k\end{array}\right)\cdot(-1)^k

    The only things that i was able to noting is if k=n we are done, because in the left-hand side is zero follow from the theorem
    \sum_{k=0}^{n}\left( \begin{array}{c}n\\k\end{array}\right)\cdot (-1)^k = 0

    and on the right-hand site we try to select an k-element subsets form a n set where n il less that k so 0.

    But im not able to generalize with binomial theorem (or by double counting).

    Thanks a lot to all
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Hint: Induction on k.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by joksy View Post
    Hi Guys first of all I would to thank in advance all people that read/try to solve this problem.

    The problem is: prove that for all positive integer k \leq n the following equality hold.
    \sum_{i=0}^{k}\left( \begin{array}{c}n\\i\end{array}\right)\cdot (-1)^i = \left( \begin{array}{c}n-1\\k\end{array}\right)\cdot(-1)^k

    The only things that i was able to noting is if k=n we are done, because in the left-hand side is zero follow from the theorem
    \sum_{k=0}^{n}\left( \begin{array}{c}n\\k\end{array}\right)\cdot (-1)^k = 0
    For N\in \mathbb{N} and \alpha \in \mathbb{R} define {{\alpha}\choose N} = \frac{\alpha(\alpha - 1)...(\alpha - N+1)}{N!} this is a generalized binomial coefficient. Fix k \in \mathbb{N}.

    Define a_n = \sum_{i=0}^{k} {n\choose i}(-1)^i and b_n = {{n-1}\choose k}(-1)^k.
    We will show \sum_{n=0}^{\infty}a_n x^n = \sum_{n=0}^{\infty} b_n x^n and it will follow that a_n = b_n.
    -----
    \sum_{n=0}^{\infty}a_n x^n = \sum_{n=0}^{\infty} \sum_{i=0}^k{n\choose i} (-1)^i x^n = \sum_{i=0}^k (-1)^i \left[ \sum_{n=0}^{\infty} {n\choose i}x^n \right]

    Now, \sum_{n=0}^{\infty} {n\choose i}x^n = \sum_{n=i}^{\infty} {n\choose i}x^n = x^i \sum_{n=0}^{\infty} {{n+i}\choose i}x^n = \frac{x^i}{(1-x)^{i+1}}

    Thus, \sum_{n=0}^{\infty}a_n x^n = \sum_{i=0}^k (-1)^k \cdot \frac{x^i}{(1-x)^{i+1}} = \frac{1}{1-x}\sum_{i=0}^k \left( \frac{x}{x-1} \right)^i = 1+ \frac{(-1)^kx^{k+1}}{(1-x)^{k+1}}
    -----
    \sum_{n=0}^{\infty}b_nx^n = (-1)^k\sum_{n=0}^{\infty}{{n-1}\choose k}x^n = (-1)^k \sum_{n=k+1}^{\infty}{{n-1}\choose k}x^n =
    .................................................. .................................. =(-1)^k x^{k+1}\sum_{n=0}^{\infty}{{n+k}\choose k}x^n
    .................................................. .................................. =\frac{(-1)^kx^{k+1}}{(1-x)^{k+1}}

    Hmm, I am not exactly sure where the mistake is and it is too late for me to check.
    They seem to be almost the same.

    EDIT: There is no mistake we have shown \sum_{n=0}^{\infty} a_n x^n = 1+\sum_{n=0}^{\infty} b_nx^n
    This means a_n = b_n for n\geq 1 and a_0 = b_0+1.
    Thus, if k < n and n\geq 1 it works out.
    Last edited by ThePerfectHacker; November 2nd 2008 at 11:10 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by ThePerfectHacker View Post
    For N\in \mathbb{N} and \alpha \in \mathbb{R} define {{\alpha}\choose N} = \frac{\alpha(\alpha - 1)...(\alpha - N+1)}{N!} this is a generalized binomial coefficient. Fix k \in \mathbb{N}.

    Define a_n = \sum_{i=0}^{k} {n\choose i}(-1)^i and b_n = {{n-1}\choose k}(-1)^k.
    We will show \sum_{n=0}^{\infty}a_n x^n = \sum_{n=0}^{\infty} b_n x^n and it will follow that a_n = b_n.
    My inductive method is a lot simpler than that. It just uses the familiar fact that {n\choose k+1} = {n-1\choose k}+{n-1\choose k+1}.

    Suppose as an inductive hypothesis that \sum_{i=0}^{k}(-1)^i{n\choose i} = (-1)^k{n-1\choose k} (the base case k=0 is clearly true). Then

    \begin{aligned}\sum_{i=0}^{k+1}(-1)^i{n\choose i} &= (-1)^k{n-1\choose k} + (-1)^{k+1}{n\choose k+1} \\ &=  (-1)^{k+1}\left\{{n\choose k+1} - {n-1\choose k}\right\} = (-1)^{k+1}{n-1\choose k+1}.\end{aligned}

    That completes the inductive step.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by joksy View Post
    Hi Guys first of all I would to thank in advance all people that read/try to solve this problem.

    The problem is: prove that for all positive integer k \leq n the following equality hold.
    \sum_{i=0}^{k}\left( \begin{array}{c}n\\i\end{array}\right)\cdot (-1)^i = \left( \begin{array}{c}n-1\\k\end{array}\right)\cdot(-1)^k

    The only things that i was able to noting is if k=n we are done, because in the left-hand side is zero follow from the theorem
    \sum_{k=0}^{n}\left( \begin{array}{c}n\\k\end{array}\right)\cdot (-1)^k = 0

    and on the right-hand site we try to select an k-element subsets form a n set where n il less that k so 0.

    But im not able to generalize with binomial theorem (or by double counting).

    Thanks a lot to all
    Hi joksy,

    You already have an excellent solution from Opalq, but here is another way to proceed:

    Consider the identity
    (1-x)^{-1} (1-x)^n = (1-x)^{n-1} \quad(*).
    Expanding the series on the left hand side, we have
    \sum_{j=0}^\infty x^j \sum_{i=0}^n (-1)^j \binom{n}{i} x^i
    The coefficient of x^k in this product is \sum_{i=0}^k (-1)^i \binom{n}{i}, while the similar coefficient on the RHS of (*) is (-1)^k \binom{n-1}{k}.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    First see here (post #4)

    Given <br />
n \in \mathbb{N},j \in \mathbb{Z}<br />
we have: <br />
\binom{n}{j} = \tfrac{1}<br />
{{2\pi }} \cdot \int_{ - \pi }^\pi  {\left( {1 + e^{ix} } \right)^n  \cdot e^{ - i \cdot x \cdot j} dx} <br />
(1) so: \sum\limits_{j = 0}^k {\binom{n}{j}}  \cdot \left( { - 1} \right)^j  = \tfrac{1}<br />
{{2\pi }} \cdot \sum\limits_{j = 0}^k {\int_{ - \pi }^\pi  {\left( {1 + e^{ix} } \right)^n  \cdot e^{ - i \cdot x \cdot j} dx} }  \cdot \left( { - 1} \right)^j  = \tfrac{1}<br />
{{2\pi }} \cdot \int_{ - \pi }^\pi {\left( {1 + e^{ix} } \right)^n \cdot \sum\limits_{j = 0}^k {\left( { - e^{ - i \cdot x} } \right)^j } dx}

    Now by the geometric sum: <br />
\sum\limits_{j = 0}^k {\left( { - e^{ - i \cdot x} } \right)^j }  = \tfrac{{e^{ix}  + \left( { - 1} \right)^k  \cdot e^{ - ix \cdot k} }}<br />
{{e^{ix}  + 1}}<br />

    Thus: <br />
\sum\limits_{j = 0}^k {\binom{n}{j}}  \cdot \left( { - 1} \right)^j  = \tfrac{1}<br />
{{2\pi }} \cdot \int_{ - \pi }^\pi  {\left( {1 + e^{ix} } \right)^{n-1}  \cdot \left[ {e^{ix}  + \left( { - 1} \right)^k  \cdot e^{ - ix \cdot k} } \right]dx}  = \left( { - 1} \right)^k  \cdot \binom{n-1}{k}<br />
- again using (1)-
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] An identity of equivalent products related to the binomial theorem
    Posted in the Differential Geometry Forum
    Replies: 8
    Last Post: September 20th 2010, 12:53 AM
  2. Binomial Theorem or Binomial Coefficient
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: October 2nd 2009, 02:06 PM
  3. Proving a binomial identity
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 16th 2009, 04:56 PM
  4. Binomial coefficiens: an identity
    Posted in the Math Challenge Problems Forum
    Replies: 2
    Last Post: April 13th 2009, 06:04 PM
  5. A binomial identity
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 13th 2008, 03:19 AM

Search Tags


/mathhelpforum @mathhelpforum