When adding zero really counts ...

Note: Although adding zero has usually no effect, there is sometimes a situation where it is the essence of a calculation which drives the development into a surprisingly fruitful direction. Here is one example of what I mean.

The Goulden-Jackson Cluster Method counts words built from a finite alphabet which are not allowed to contain so-called bad words. This method nicely presented (and something to chuckling about) by J. Noonan and D. Zeilberger is very efficient and the reason for it's efficiency is due to a clever addition of zeros.

Let's denote the alphabet $V$, the language $\mathcal{L}$ and let $B$ be the set of bad words. Since we want to work with generating functions, we introduce weights on words $$weight(w):=s^{length(w)}$$

The generating function $f(s)$ is the weight enumerator of the set of valid words $\mathcal{L}(B)$ that avoids the members of $B$ as factors (i.e. substrings). We obtain \begin{align*} f(s)=\sum_{w\in\mathcal{L}(B)}weight(w) \end{align*}

It turns out according to the first section in the referred paper that counting these words is a cumbersome job. In fact we can do it much better and the trick is to add $0$ to both sides and

rewrite this expression as \begin{align*} f(s)=\sum_{w\in V^*}weight(w)0^{[\text{number of factors of }w\text{ that belong to }B]} \end{align*} and then use the following deep facts (wording from the paper :-) ) \begin{align*} 0&=1+(-1)\\ 0^r&= \begin{cases} 1,&\text{if }r=0\\ 0,&\text{if }r>0 \end{cases} \end{align*} and for any finite set $A$, \begin{align*} \prod_{a\in A}0=\prod_{a\in A}(1+(-1))=\sum_{S\subset A}(-1)^{|S|} \end{align*} where $|S|$ denotes the cardinality of $S$.

We now have \begin{align*} f(s)&=\sum_{w\in V^*}weight(w)0^{[\text{number of factors of }w\text{ that belong to }B]}\\ &=\sum_{w\in V^*}weight(w)(1+(-1))^{[\text{number of factors of }w\text{ that belong to }B]}\\ &=\sum_{w\in V^*}\sum_{S\subset\text{Bad}(w)}(-1)^{|S|}s^{\text{length}(w)} \end{align*} where Bad$(w)$ is the set of factors of $w$ that belong to $B$.

This clever usage of the Inclusion-exclusion principle is a much more superior approach to calculate the valid words not containing any bad factors and the essence was to add zero in order to introduce the IEP.

So, my question is: Do you know from other situations where cleverly adding $0$ or multiplying with $1$ opens up a door to solve a problem.

Solution 1:

Filter polynomial coefficients by cleverly adding zeros

We consider the polynomial \begin{align*} (1+x+x^2)^n=\sum_{j=0}^{2n}a_jx^j \end{align*} and want to find \begin{align*} \sum_{{j=0}\atop{j \equiv 0(3)}}^{2n}a_j=a_0+a_3+a_6+\cdots\tag{1} \end{align*}

Of course we can evaluate $(1+x+x^2)^n$ at $x=1$ to get \begin{align*} 3^n=\sum_{j=0}^{2n}a_j\tag{2} \end{align*} But how can we filter the coefficients to obtain (1)? Cleverly adding zeros will help.

We consider the $3^\text{rd}$ roots of unity \begin{align*} \omega_1=\exp\left(\frac{2\pi i}{3}\right)\qquad\qquad \omega_2=\exp\left(\frac{4\pi i}{3}\right)=\omega_1^2\tag{3} \end{align*} and use the nice property that the sum of all $m$-th roots of unity sum to $0$ iff $m> 1$: \begin{align*} 1+\omega_1+\omega_2=0 \end{align*}

It follows when evaluating $1+x+x^2$ at $\omega_1$ and $\omega_2$: \begin{align*} 1+\omega_1+\omega_1^2=1+\omega_1+\omega_2\color{blue}{=0}\\ 1+\omega_2+\omega_2^2=1+\omega_2+\omega_1\color{blue}{=0} \end{align*}

Adding these zeros to (2) does the job. We evaluate $(1+x+x^2)^n$ at $1,\omega_1$ and $\omega_2$. We obtain using (3)

\begin{align*} 3^n\color{blue}{+0+0}&=(1+1+1)^n +(1+\omega_1+\omega_1^2)^n+(1+\omega_2+\omega_2^2)^n\\ &=\sum_{j=0}^{2n}a_j+\sum_{j=0}^{2n}a_j\omega_1^j+\sum_{j=0}^{2n}a_j\omega_2^j\\ &=\sum_{j=0}^{2n}a_j+\left(\sum_{{j=0}\atop{j\equiv 0(3)}}^{2n}a_j+\sum_{{j=0}\atop{j\equiv 1(3)}}^{2n}a_j\omega_1+\sum_{{j=0}\atop{j\equiv 2(3)}}^{2n}a_j\omega_1^2\right)\\ &\qquad\qquad+\left(\sum_{{j=0}\atop{j\equiv 0(3)}}^{2n}a_j+\sum_{{j=0}\atop{j\equiv 1(3)}}^{2n}a_j\omega_2+\sum_{{j=0}\atop{j\equiv 2(3)}}^{2n}a_j\omega_2^2\right)\\ &=3\sum_{{j=0}\atop{j\equiv 0(3)}}^{2n}a_j +\sum_{{j=0}\atop{j\equiv 1(3)}}^{2n}a_j\left(1+\omega_1+\omega_2\right) +\sum_{{j=0}\atop{j\equiv 2(3)}}^{2n}a_j\left(1+\omega_1^2+\omega_2^2\right)\\ &=3\sum_{{j=0}\atop{j\equiv 0(3)}}^{2n}a_j +\sum_{{j=0}\atop{j\equiv 1(3)}}^{2n}a_j\left(\color{blue}{1+\omega_1+\omega_2}\right) +\sum_{{j=0}\atop{j\equiv 2(3)}}^{2n}a_j\left(\color{blue}{1+\omega_2+\omega_1}\right)\\ &=3\sum_{{j=0}\atop{j\equiv 0(3)}}^{2n}a_j \end{align*}

and we finally conclude

\begin{align*} \color{blue}{\sum_{{j=0}\atop{j\equiv 0(3)}}^{2n}a_j=3^{n-1}\qquad\qquad n\geq 1} \end{align*}

Note: This is a rewrite of this answer based upon a comment there from @labbhattacharjee.

Solution 2:

There are many different ways to prove the binomial identity \begin{align*} \sum_{j=0}^{n}(-1)^j\binom{m}{j}=(-1)^n\binom{m-1}{n}\tag{1} \end{align*} where $n$ is a non-negative integer and $m\in\mathbb{C}$.

A nice little gem does the job by cleverly multiplying the left hand-side of (1) with $(\pm)1$. We obtain \begin{align*} \sum_{j=0}^{n}(-1)^j\binom{m}{j} &=\sum_{j=0}^{n}(-1)^j\binom{m}{j}\color{blue}{\cdot 1}\\ &=\sum_{j=0}^{n}(-1)^j\binom{m}{j}\color{blue}{\binom{n-j}{n-j}}\\ &=\color{blue}{(-1)^n}\sum_{j=0}^{n}\binom{m}{j}\color{blue}{\binom{-1}{n-j}}\tag{2}\\ &=(-1)^n\binom{m-1}{n}\tag{3} \end{align*}

Comment:

• In (2) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.

• In (3) we apply the Chu-Vandermonde Identity.

Note: This contribution is thanks to this MSE post by @robjohn.

Solution 3:

Here is an example for your list. It is problem 1 in W. Sierpinski's "250 Problems in Elementary Number Theory".

The question is to find all $n$ such that $n + 1 | n^2 + 1$. The answer is that $n = 1$ is the only solution.

Although Sierpinski does not include these intermediate steps in his solution, here is how one might include those steps in order to meet your requirements:

$$n^2 + 1 = n^2 + 1 + 0 = n^2 + 1 + (n - n) = (n^2 + n) - n + 1 = n(n + 1) - (n - 1)$$

One can see that if $n + 1$ divides $n^2 + 1$, then it must also divide $n - 1$.

Solution 4:

When trying to prove that $$ \sum^{j}_{k = i} (-1)^{j + k} \binom{j}{k} \binom{k}{i} = \delta_{i j} $$ (which is related to this porblem ) one can start with $x$ and expand the expression by adding 0, with the goal of getting two binomial coefficents. \begin{align*} x^{j} &= (x + 0)^j = (x +1 -1)^j =((x +1 ) -1 )^{j} \\ &= \sum^{j}_{k = 0} \binom{j}{k} (x + 1)^{k} \underbrace{ (-1)^{j - k} }_{= (-1)^{j - k + 2 k}} = \sum^{j}_{k = 0} (-1)^{j + k} \binom{j}{k} (x + 1)^{k} \\ &= \sum^{j}_{k = 0} (-1)^{j + k} \binom{j}{k} \sum^{k}_{i = 0} \binom{k}{i} x^{i} = \sum^{j}_{k = 0} \sum^{k}_{i = 0} (-1)^{j + k} \binom{j}{k} \binom{k}{i} x^{i} \\ &= \sum^{j}_{i = 0} \sum^{j}_{k = i} (-1)^{j + k} \binom{j}{k} \binom{k}{i} x^{i} \\ \end{align*} Comparing the polynomials on each side then gives the desired result.