Prove S(n,m)=S(m,n)

For discussing Olympiad Level Combinatorics problems
User avatar
asif e elahi
Posts:185
Joined:Mon Aug 05, 2013 12:36 pm
Location:Sylhet,Bangladesh
Prove S(n,m)=S(m,n)

Unread post by asif e elahi » Sun Aug 24, 2014 7:33 pm

Let m,n be positive integers and let
$S(m,n)=\dbinom{n}{0}(2^n-1)^m-\dbinom{n}{1}(2^{n-1}-1)^m+\dbinom{n}{2}(2^{n-2}-1)^m+ \cdots $ $+(-1)^{n-1}\dbinom{n}{n-1}$
Prove $S(n,m)=S(m,n)$

User avatar
Fatin Farhan
Posts:75
Joined:Sun Mar 17, 2013 5:19 pm
Location:Kushtia,Bangladesh.
Contact:

Re: Prove S(n,m)=S(m,n)

Unread post by Fatin Farhan » Mon Aug 25, 2014 7:01 pm

$$\begin{eqnarray*} \\
&& S(m,n)= \sum_{i=0}^{n-1} (-1)^i \dbinom{n}{i} (2^{n-i}-1)^m \cdots(1)
\end{eqnarray*}$$
In the expression of (1),
$$\begin{eqnarray*} \\
&&\binom{n}{0} (-1)^m \binom {m}{m}(2^n)^0- \binom{n}{1} (-1)^m \binom {m}{m}(2^n)^0+\binom{n}{2} (-1)^m \binom {m}{m}(2^n)^0 \\
&& +\cdots+ \dbinom{n}{n-1} (-1)^{n-1} (-1)^{m} \binom {m}{m}(2^n)^0 \\
&&= \binom{n}{0} (-1)^m - \binom{n}{1} (-1)^m +\binom{n}{2} (-1)^m \\
&& + \cdots+ \dbinom{n}{n-1} (-1)^{n-1} (-1)^{m} + \dbinom{n}{n} (-1)^{n} (-1)^{m} \\
&&-\dbinom{n}{n} (-1)^{n} (-1)^{m} \\
\end{eqnarray*}$$

$$\begin{eqnarray*} \\
&&=(-1)^{m} \left(\binom{n}{0} - \binom{n}{1} +\binom{n}{2}
+ \cdots+ \dbinom{n}{n-1} (-1)^{n-1} + \dbinom{n}{n} (-1)^{n} \right)
- (-1)^{m}(-1)^{n}
\end{eqnarray*}$$

$$\begin{eqnarray*} \\
&&=- (-1)^{m}(-1)^{n} \\
\end{eqnarray*}$$

$$\begin{eqnarray*} \\
&&=(-1)^{n} \left(\binom{m}{0} - \binom{m}{1} +\binom{m}{2}
+ \cdots+ \dbinom{m}{m-1} (-1)^{m-1} + \dbinom{m}{m} (-1)^{m} \right)
- (-1)^{m}(-1)^{n}
\end{eqnarray*}$$

$$\begin{eqnarray*} \\
&&=(-1)^{n} \left(\binom{m}{0} - \binom{m}{1} +\binom{m}{2}
+ \cdots+ \dbinom{m}{m-1} (-1)^{m-1} \right)
\end{eqnarray*}$$

$$\begin{eqnarray*} \\
&&=\binom{m}{0} (-1)^n \binom {n}{n}(2^m)^0- \binom{m}{1} (-1)^n \binom {n}{n}(2^m)^0+\binom{m}{2} (-1)^n \binom {n}{n}(2^m)^0 \\

\end{eqnarray*}$$


$$
\begin{eqnarray*} \\
&&\therefore S(m,n) \\
&&=\sum_{i=0}^{n-1} (-1)^i \dbinom{n}{i} (2^{n-i}-1)^m \\
&&=\sum_{i=0}^{m-1} (-1)^i \dbinom{m}{i} (2^{m-i}-1)^n\\
&&=S(n,m)
\end{eqnarray*}$$
:mrgreen: :mrgreen:
Last edited by Fatin Farhan on Tue Aug 26, 2014 11:24 am, edited 1 time in total.
"The box said 'Requires Windows XP or better'. So I installed L$$i$$nux...:p"

Nirjhor
Posts:136
Joined:Thu Aug 29, 2013 11:21 pm
Location:Varies.

Re: Prove S(n,m)=S(m,n)

Unread post by Nirjhor » Mon Aug 25, 2014 11:54 pm

\[\begin{eqnarray}
S(m,n)+\left(-1\right)^{m+n} &= &\sum_{i=0}^n \left(-1\right)^i \dbinom{n}{i} \left(2^{n-i}-1\right)^m~~~\left[\text{compact form}\right] \\
&= &\sum_{i=0}^n \left(-1\right)^i \dbinom{n}{i} \left(\sum_{k=0}^m \dbinom{m}{k}\left(-1\right)^k 2^{(m-k)(n-i)}\right) ~~~\left[\text{binomial theorem}\right]\\
&=& \sum_{i=0}^n \sum_{k=0}^m \dbinom{m}{k} \dbinom{n}{i} \left(-1\right)^{k+i} 2^{(m-k)(n-i)} ~~~\left[\text{multiplying out}\right]\\
&=& \sum_{k=0}^m \sum_{i=0}^n \dbinom{m}{k} \dbinom{n}{i} \left(-1\right)^{k+i} 2^{(m-k)(n-i)}~~~\left[\text{interchanging order}\right] \\
&=& S(n,m)+\left(-1\right)^{m+n} ~~~\left[\text{by symmetry}\right]. \\
\end{eqnarray}\]
- What is the value of the contour integral around Western Europe?

- Zero.

- Why?

- Because all the poles are in Eastern Europe.


Revive the IMO marathon.

User avatar
asif e elahi
Posts:185
Joined:Mon Aug 05, 2013 12:36 pm
Location:Sylhet,Bangladesh

Re: Prove S(n,m)=S(m,n)

Unread post by asif e elahi » Tue Aug 26, 2014 5:58 pm

I was looking for a beautiful solution without calculation.May be there is a solution using PIE and bijection.I tried to find one,but failed. :cry: :cry:

Post Reply