# Thread: Identity using binomial theorem

1. ## 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

2. Hint: Induction on k.

3. Originally Posted by joksy
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.

4. Originally Posted by ThePerfectHacker
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.

5. Originally Posted by joksy
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}$.

6. 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)-