Identity using binomial theorem

Printable View

November 1st 2008, 06:15 AM
joksy

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
November 1st 2008, 09:10 AM
Opalg

Hint: Induction on k.
November 1st 2008, 07:12 PM
ThePerfectHacker

Quote:

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 $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. (Sleepy)
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.
November 2nd 2008, 01:17 AM
Opalg

Quote:

Originally Posted by ThePerfectHacker

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.
November 2nd 2008, 07:41 AM
awkward

Quote:

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 $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}$ .
November 2nd 2008, 09:41 AM
PaulRS

First see here (post #4)

Given $ n \in \mathbb{N},j \in \mathbb{Z} $ we have: $ \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: $\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$ $= \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: $ \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: $ \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)-