Results 1 to 6 of 6

Thread: 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 $\displaystyle k \leq n $ the following equality hold.
    $\displaystyle \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
    $\displaystyle \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
    10
    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 $\displaystyle k \leq n $ the following equality hold.
    $\displaystyle \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
    $\displaystyle \sum_{k=0}^{n}\left( \begin{array}{c}n\\k\end{array}\right)\cdot (-1)^k = 0$
    For $\displaystyle N\in \mathbb{N}$ and $\displaystyle \alpha \in \mathbb{R}$ define $\displaystyle {{\alpha}\choose N} = \frac{\alpha(\alpha - 1)...(\alpha - N+1)}{N!}$ this is a generalized binomial coefficient. Fix $\displaystyle k \in \mathbb{N}$.

    Define $\displaystyle a_n = \sum_{i=0}^{k} {n\choose i}(-1)^i$ and $\displaystyle b_n = {{n-1}\choose k}(-1)^k$.
    We will show $\displaystyle \sum_{n=0}^{\infty}a_n x^n = \sum_{n=0}^{\infty} b_n x^n $ and it will follow that $\displaystyle a_n = b_n$.
    -----
    $\displaystyle \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, $\displaystyle \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, $\displaystyle \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}}$
    -----
    $\displaystyle \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 = $
    .................................................. ..................................$\displaystyle =(-1)^k x^{k+1}\sum_{n=0}^{\infty}{{n+k}\choose k}x^n$
    .................................................. ..................................$\displaystyle =\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 $\displaystyle \sum_{n=0}^{\infty} a_n x^n = 1+\sum_{n=0}^{\infty} b_nx^n $
    This means $\displaystyle a_n = b_n$ for $\displaystyle n\geq 1$ and $\displaystyle a_0 = b_0+1$.
    Thus, if $\displaystyle k < n$ and $\displaystyle n\geq 1$ it works out.
    Last edited by ThePerfectHacker; Nov 2nd 2008 at 10: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
    10
    Quote Originally Posted by ThePerfectHacker View Post
    For $\displaystyle N\in \mathbb{N}$ and $\displaystyle \alpha \in \mathbb{R}$ define $\displaystyle {{\alpha}\choose N} = \frac{\alpha(\alpha - 1)...(\alpha - N+1)}{N!}$ this is a generalized binomial coefficient. Fix $\displaystyle k \in \mathbb{N}$.

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

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

    $\displaystyle \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 $\displaystyle k \leq n $ the following equality hold.
    $\displaystyle \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
    $\displaystyle \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
    $\displaystyle (1-x)^{-1} (1-x)^n = (1-x)^{n-1} \quad(*)$.
    Expanding the series on the left hand side, we have
    $\displaystyle \sum_{j=0}^\infty x^j \sum_{i=0}^n (-1)^j \binom{n}{i} x^i$
    The coefficient of $\displaystyle x^k$ in this product is $\displaystyle \sum_{i=0}^k (-1)^i \binom{n}{i}$, while the similar coefficient on the RHS of (*) is $\displaystyle (-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 $\displaystyle
    n \in \mathbb{N},j \in \mathbb{Z}
    $ we have: $\displaystyle
    \binom{n}{j} = \tfrac{1}
    {{2\pi }} \cdot \int_{ - \pi }^\pi {\left( {1 + e^{ix} } \right)^n \cdot e^{ - i \cdot x \cdot j} dx}
    $ (1) so: $\displaystyle \sum\limits_{j = 0}^k {\binom{n}{j}} \cdot \left( { - 1} \right)^j = \tfrac{1}
    {{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 $$\displaystyle = \tfrac{1}
    {{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: $\displaystyle
    \sum\limits_{j = 0}^k {\left( { - e^{ - i \cdot x} } \right)^j } = \tfrac{{e^{ix} + \left( { - 1} \right)^k \cdot e^{ - ix \cdot k} }}
    {{e^{ix} + 1}}
    $

    Thus: $\displaystyle
    \sum\limits_{j = 0}^k {\binom{n}{j}} \cdot \left( { - 1} \right)^j = \tfrac{1}
    {{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}
    $ - 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: Sep 19th 2010, 11:53 PM
  2. Binomial Theorem or Binomial Coefficient
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: Oct 2nd 2009, 01:06 PM
  3. Proving a binomial identity
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Apr 16th 2009, 03:56 PM
  4. Binomial coefficiens: an identity
    Posted in the Math Challenge Problems Forum
    Replies: 2
    Last Post: Apr 13th 2009, 05:04 PM
  5. A binomial identity
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 13th 2008, 02:19 AM

Search Tags


/mathhelpforum @mathhelpforum