The binomial formula and the value of $0^0$

Question

Here is the text from Knuth's The Art of computer programming, 1.2.6 F formula 14:

Knuth doesn't give the proof of the statement. So, I tried to write it myself.

To make binomial formula equal to $0^0$, it must satisfy the following conditions:

$ \left\{ \begin{aligned} x = -y\\ r = 0\\ \end{aligned} \right. $

By definition:

$ {n\choose k}=\frac{n!}{k!(n-k)!} $

If $k < 0$ or $k > n$, the coefficient is equal to 0 (provided that n is a nonnegative integer) - 1.2.6 B.

and if $r = 0$, we have:

$ {0\choose k} $

which is non-zero only when k = 0:

$ {0\choose 0} = \frac{0!}{0!(0-0)!} = \frac{1}{1} = 1 $

So, putting our conditions into the formula, we get:

$ (x + (-x))^0 = {0\choose 0} x^0(-x)^0 = 1\cdot1\cdot1 = 1 $

Therefore, $0^0 = 1$

Is my proof correct?

Also this page: http://mathworld.wolfram.com/Power.html says, that $0^0$ itself is undefined, although defining $0^0=1$ allows some formulas to be expressed simply (Knuth 1992; Knuth 1997, p. 57).

But he is not defining it to be equal to 1, he is deducing this fact from binomial theorem. Plus Knuth doesn't say on page 57 (which is provided), what formulas can be expressed simply. Is the statement about Knuth on mathworld not fully correct?

Answer 1

I think you do not interpret the text as it was intended. What Knuth is saying is that the binomial formula as stated cannot be valid unless one defines $0^0=1$. He says so more clearly in his 1992 article Two notes on notation (page 6, equation (1.18)):

Anybody who wants the binomial theorem $$(x + y)^n =\sum_{k=0}^n\binom nk x^ky^{n−k}$$ to hold for at least one nonnegative integer $n$ must believe that $0^0 = 1$, for we can plug in $x = 0$ and $y = 1$ to get $1$ on the left and $0^0$ on the right.

Indeed one has for instance $1=(0+1)^2=\binom20.0^0.1^2+\binom21.0^1.1^1+\binom22.0^2.1^0$, and the right hand side reduces to $0^0$ because the last two terms vanish because of the non-controversial evaluations $0^1=0^2=0$.

So in particular, this does not just involve the case of the binomial theorem for exponent$~0$; the point is that exponents$~0$ occur on the in the right hand side for every instance of the binomial formula.

Note that one usually does not encounter this case explicitly because of our habit of contracting the term $\binom n0x^0y^n$ to $y^n$ whenever we write explicit instances of the binomial formula. Your citation illustrates this, as Knuth writes terms $x^4$ and $y^4$ in his explicit instance of the binomial formula for $r=4$. (It also illustrates another common peculiarity: in explicit instances of the binomial formula we tend to take the summation index decreasing from $n$ to $0$, or what amounts to the same use a variant of the formula in which the exponents of $x$ and $y$ are interchanged.)

Indeed, the most important reason we are not confronted with instances of $0^0$ (and therefore with the need to have it well defined) all the time is, that we have learned the habit, similar to that of suppressing explicit terms$~0$ in a summation or factors$~1$ in a product, of immediately replacing any expression $x^0$ by$~1$ (or simply omitting it if occurring in a product). I consider this a nice paradox of human psychology:

The fact that people can maintain that $0^0$ should be left undefined depends on the circumstance that instances of the expression almost never occur when doing mathematics. This state of affairs is a consequence of the habit of systematically suppressing multiplicative factors of the form$~x^0$ when writing formulas. This notwithstanding the fact that the equation $x^0=1$ implicitly applied during this suppression can only be justified if $x^0$ is always defined, in particular for $x=0$.

Answer 2

By choosing this way of arriving at $0^0$ and assigning it the value $1$ without any other qualifying statements, Knuth has in fact made a definition of sorts. So the Mathworld article is correct.

Also, I see your proof as valid for the given result. By choosing the mechanisms you have, you arrived at that particular value of $0^0$. This is similar to what happens when the terms of a conditionally convergent series are rearranged: it is almost always possible to get any value desired as the result. A better term for this is "indeterminate" rather than "undefined" as the Mathworld article notes.

Basically, by choosing the Binomial Formula as the context, you have chosen the value that $0^0$ will have. This does not change the fact that $0^0$ is indeterminate when considered without context.

$0^0$ is truly indeterminate in general, but Knuth and your proof are saying $(0+x)^0 = 1$ is expressible as $0^0 = 1$. You have chosen a specific context, and within that context $0^0$ evaluates to $1$.

Another way to say this is that $1^0 = 1$ may also be expressed as "$0^0$ can take on the value $1$", but this does not convey any more information than saying that "${\infty \over \infty}$ can take on the value $1$".

Even in Computer Science, defining $0^0 = 1$ is dangerous as there may be (read: there are always) situations in which this is an incorrect result. Consider interval arithmetic as a way of handling the expression $0^0$ properly within a computer.

Consider the following examples: what is the value of $\lim_{x \to 1} (1-x)^{x-1}$? $\lim_{x \to 0} (\cos(x) - 1)^x$?

Answer 3

EDIT

1. If $0^0$ assumed to be undefined and empty sums (those with a lower limit greater than upper limit) are assumed to be zero, use:

   $(x+y)^n =x^n + \sum_{k=1}^{n-1} (_k^n)x^k y^{n-k} +y^n~~~~~$ for $n\ge 1$

   $~~~~~~~~~~~~~~= 1~~~~~~~~~~~~$ for $n=0$ and $x+y\ne 0\\$

2. If both $0^0$ and empty sums are assumed to be undefined, use:

   $(x+y)^n =x^n + \sum_{k=1}^{n-1} (_k^n)x^k y^{n-k} +y^n~~~~~$ for $n\gt 1$

   $~~~~~~~~~~~~~~= x+y~~~~~$ for $n=1$

   $~~~~~~~~~~~~~~= 1~~~~~~~~~~~~$ for $n=0$ and $x+y\ne 0$

Results in both cases will be consistent with the standard formula except for $(x+y)^0$ being undefined when $x+y=0$.

Answer 4

To the best of my knowledge, the convention that $0^0$ is undefined serves one purpose, namely to avoid a discontinuity of the function $x\mapsto 0^x$ at $0$ (or the function $x^y$ at $(0,0)$). This has value when people (primarily calculus students) think that limits like $\lim_{t\to a}f(t)^{g(t)}$ should be evaluated by plugging $a$ in place of $t$ in $f(t)^{g(t)}$. A discontinuity will cause this method to give the wrong answer when the plugging-in gives $0^0$. Ideally, our calculus students would learn that you have to ascertain continuity before using the plug-in method. In our non-ideal world, a good number of them don't learn that, and so we teach them that $0^0$ is undefined. That way, the result of plugging in will not give them a wrong answer; it will refuse to give them an answer, so it will force them to do something better than plugging in (e.g., take logarithms and try L'Hopital's rule).

But I think the "undefined" convention is useful only for people who might (unknowingly) assume continuity where there is in fact a discontinuity. For the rest of us, $0^0$ should be $1$.

Note, by the way, that the point of discontinuity is at the edge of the domain of definition of $0^y$ (or $x^y$), so it's not particularly surprising (to me) that something strange, from the point of view of analysis, happens there.