2d. Basic functions

[math] \newcommand{\mathds}{\mathbb}[/math]

This article was automatically generated from a tex file and may contain conversion errors. If permitted, you may login and edit this article to improve the conversion.

With the above theory in hand, let us get now to interesting things, namely computations. Among others, because this is what a mathematician's job is, doing all sorts of computations. We will be mainly interested in the functions [math]x^a[/math] and [math]a^x[/math], which remain something quite mysterious. Regarding [math]x^a[/math], we first have the following result:

Theorem

We have the generalized binomial formula

[[math]] (1+x)^a=\sum_{k=0}^\infty\binom{a}{k}x^k [[/math]]

with the generalized binomial coefficients being given by

[[math]] \binom{a}{k}=\frac{a(a-1)\ldots(a-k+1)}{k!} [[/math]]

valid for any exponent [math]a\in\mathbb Z[/math], and any [math]|x| \lt 1[/math].

Show Proof

This is something quite tricky, the idea being as follows:

(1) For exponents [math]a\in\mathbb N[/math], this is something that we know well from chapter 1, and which is valid for any [math]x\in\mathbb R[/math], coming from the usual binomial formula, namely:

[[math]] (1+x)^n=\sum_{k=0}^n\binom{n}{k}x^k [[/math]]

(2) For the exponent [math]a=-1[/math] this is something that we know from chapter 1 too, coming from the following formula, valid for any [math]|x| \lt 1[/math]:

[[math]] \frac{1}{1+x}=1-x+x^2-x^3+\ldots [[/math]]

Indeed, this is exactly our generalized binomial formula at [math]a=-1[/math], because:

[[math]] \binom{-1}{k} =\frac{(-1)(-2)\ldots(-k)}{k!} =(-1)^k [[/math]]

(3) Let us discuss now the general case [math]a\in-\mathbb N[/math]. With [math]a=-n[/math], and [math]n\in\mathbb N[/math], the generalized binomial coefficients are given by the following formula:

[[math]] \begin{eqnarray*} \binom{-n}{k} &=&\frac{(-n)(-n-1)\ldots(-n-k+1)}{k!}\\ &=&(-1)^k\frac{n(n+1)\ldots(n+k-1)}{k!}\\ &=&(-1)^k\frac{(n+k-1)!}{(n-1)!k!}\\ &=&(-1)^k\binom{n+k-1}{n-1} \end{eqnarray*} [[/math]]

Thus, our generalized binomial formula at [math]a=-n[/math], and [math]n\in\mathbb N[/math], reads:

[[math]] \frac{1}{(1+t)^n}=\sum_{k=0}^\infty(-1)^k\binom{n+k-1}{n-1}t^k [[/math]]

(4) In order to prove this formula, it is convenient to write it with [math]-t[/math] instead of [math]t[/math], in order to get rid of signs. The formula to be proved becomes:

[[math]] \frac{1}{(1-t)^n}=\sum_{k=0}^\infty\binom{n+k-1}{n-1}t^k [[/math]]

We prove this by recurrence on [math]n[/math]. At [math]n=1[/math] this formula definitely holds, as explained in (2) above. So, assume that the formula holds at [math]n\in\mathbb N[/math]. We have then:

[[math]] \begin{eqnarray*} \frac{1}{(1-t)^{n+1}} &=&\frac{1}{1-t}\cdot\frac{1}{(1-t)^n}\\ &=&\sum_{k=0}^\infty t^k\sum_{l=0}^\infty\binom{n+l-1}{n-1}t^l\\ &=&\sum_{s=0}^\infty t^s\sum_{l=0}^s\binom{n+l-1}{n-1} \end{eqnarray*} [[/math]]

On the other hand, the formula that we want to prove is:

[[math]] \frac{1}{(1-t)^{n+1}}=\sum_{s=0}^\infty\binom{n+s}{n}t^k [[/math]]

Thus, in order to finish, we must prove the following formula:

[[math]] \sum_{l=0}^s\binom{n+l-1}{n-1}=\binom{n+s}{n} [[/math]]

(5) In order to prove this latter formula, we proceed by recurrence on [math]s\in\mathbb N[/math]. At [math]s=0[/math] the formula is trivial, [math]1=1[/math]. So, assume that the formula holds at [math]s\in\mathbb N[/math]. In order to prove the formula at [math]s+1[/math], we are in need of the following formula:

[[math]] \binom{n+s}{n}+\binom{n+s}{n-1}=\binom{n+s+1}{n} [[/math]]

But this is the Pascal formula, that we know from chapter 1, and we are done.

■

Quite interestingly, the formula in Theorem 2.29 holds in fact at any [math]a\in\mathbb R[/math], but this is something non-trivial, whose proof will have to wait until chapter 3 below. However, in the meantime, let us investigate the case [math]a\in\mathbb Z/2[/math]. Indeed, not only the results here are interesting, and very useful in practice, but also they can be proved with elementary methods. At [math]a=\pm 1/2[/math], to start with, we have the following result:

Theorem

The generalized binomial formula, namely

[[math]] (1+x)^a=\sum_{k=0}^\infty\binom{a}{k}x^k [[/math]]

holds as well at [math]a=\pm1/2[/math]. In practice, at [math]a=1/2[/math] we obtain the formula

[[math]] \sqrt{1+t}=1-2\sum_{k=1}^\infty C_{k-1}\left(\frac{-t}{4}\right)^k [[/math]]

with [math]C_k=\frac{1}{k+1}\binom{2k}{k}[/math] being the Catalan numbers, and at [math]a=-1/2[/math] we obtain

[[math]] \frac{1}{\sqrt{1+t}}=\sum_{k=0}^\infty D_k\left(\frac{-t}{4}\right)^k [[/math]]

with [math]D_k=\binom{2k}{k}[/math] being the central binomial coefficients.

Show Proof

This can be done in several steps, as follows:

(1) At [math]a=1/2[/math], the generalized binomial coefficients are as follows:

[[math]] \begin{eqnarray*} \binom{1/2}{k} &=&\frac{1/2(-1/2)\ldots(3/2-k)}{k!}\\ &=&(-1)^{k-1}\frac{1\cdot 3\cdot 5\ldots(2k-3)}{2^kk!}\\ &=&(-1)^{k-1}\frac{(2k-2)!}{2^{k-1}(k-1)!2^kk!}\\ &=&-2\left(\frac{-1}{4}\right)^kC_{k-1} \end{eqnarray*} [[/math]]

(2) At [math]a=-1/2[/math], the generalized binomial coefficients are as follows:

[[math]] \begin{eqnarray*} \binom{-1/2}{k} &=&\frac{-1/2(-3/2)\ldots(1/2-k)}{k!}\\ &=&(-1)^k\frac{1\cdot 3\cdot 5\ldots(2k-1)}{2^kk!}\\ &=&(-1)^k\frac{(2k)!}{2^kk!2^kk!}\\ &=&\left(\frac{-1}{4}\right)^kD_k \end{eqnarray*} [[/math]]

(3) Summarizing, we have proved so far that the binomial formula at [math]a=\pm1/2[/math] is equivalent to the explicit formulae in the statement, involving the Catalan numbers [math]C_k[/math], and the central binomial coefficients [math]D_k[/math]. It remains now to prove that these two explicit formulae hold indeed. For this purpose, let us write these formulae as follows:

[[math]] \sqrt{1-4t}=1-2\sum_{k=1}^\infty C_{k-1}t^k\quad,\quad \frac{1}{\sqrt{1-4t}}=\sum_{k=0}^\infty D_kt^k [[/math]]

In order to check these latter formulae, we must prove the following identities:

[[math]] \left(1-2\sum_{k=1}^\infty C_{k-1}t^k\right)^2=1-4t\quad,\quad \left(\sum_{k=0}^\infty D_kt^k\right)^2=\frac{1}{1-4t} [[/math]]

(4) As a first observation, the formula on the left is equivalent to:

[[math]] \sum_{k+l=n}C_kC_l=C_{n+1} [[/math]]

By using the series for [math]1/(1-4t)[/math], the formula on the right is equivalent to:

[[math]] \sum_{k+l=n}D_kD_l=4^n [[/math]]

Finally, observe that if our formulae hold indeed, by multiplying we must have:

[[math]] \sum_{k+l=n}C_kD_l=\frac{D_{n+1}}{2} [[/math]]

(5) Summarizing, we have to understand 3 formulae, which look quite similar. Let us first attempt to prove [math]\sum_{k+l=n}D_kD_l=4^n[/math], by recurrence. We have:

[[math]] D_{k+1}=\binom{2k+2}{k+1}=\frac{4k+2}{k+1}\binom{2k}{k}=\left(4-\frac{2}{k+1}\right)D_k [[/math]]

Thus, assuming that we have [math]\sum_{k+l=n}D_kD_l=4^n[/math], we obtain:

[[math]] \begin{eqnarray*} \sum_{k+l=n+1}D_kD_l &=&D_0D_{n+1}+\sum_{k+l=n}\left(4-\frac{2}{k+1}\right)D_kD_l\\ &=&D_{n+1}+4\sum_{k+l=n}D_kD_l-2\sum_{k+l=n}\frac{D_kD_l}{k+1}\\ &=&D_{n+1}+4^{n+1}-2\sum_{k+l=n}C_kD_l \end{eqnarray*} [[/math]]

Thus, this leads to a sort of half-failure, the conclusion being that for proving by recurrence the second formula in (4), we need the third formula in (4).

(6) All this suggests a systematic look at the three formulae in (4). According to our various observations above, these three formulae are equivalent, and so it is enough to prove one of them. We will chose here to prove the first one, namely:

[[math]] \sum_{k+l=n}C_kC_l=C_{n+1} [[/math]]

(7) For this purpose, we will trick. Let us count the Dyck paths in the plane, which are by definition the paths from [math](0,0)[/math] to [math](n,n)[/math], marching North-East over the integer lattice [math]\mathbb Z^2\subset\mathbb R^2[/math], by staying inside the square [math][0,n]\times[0,n][/math], and staying as well under the diagonal of this square. As an example, here are the 5 possible Dyck paths at [math]n=3[/math]:

[[math]] \xymatrix@R=4pt@C=4pt {\circ&\circ&\circ&\circ\\ \circ&\circ&\circ&\circ\ar@{-}[u]\\ \circ&\circ&\circ&\circ\ar@{-}[u]\\ \circ\ar@{-}[r]&\circ\ar@{-}[r]&\circ\ar@{-}[r]&\circ\ar@{-}[u]} \qquad \item[a]ymatrix@R=4pt@C=4pt {\circ&\circ&\circ&\circ\\ \circ&\circ&\circ&\circ\ar@{-}[u]\\ \circ&\circ&\circ\ar@{-}[r]&\circ\ar@{-}[u]\\ \circ\ar@{-}[r]&\circ\ar@{-}[r]&\circ\ar@{-}[u]&\circ} \qquad \item[a]ymatrix@R=4pt@C=4pt {\circ&\circ&\circ&\circ\\ \circ&\circ&\circ\ar@{-}[r]&\circ\ar@{-}[u]\\ \circ&\circ&\circ\ar@{-}[u]&\circ\\ \circ\ar@{-}[r]&\circ\ar@{-}[r]&\circ\ar@{-}[u]&\circ} \qquad \item[a]ymatrix@R=4pt@C=4pt {\circ&\circ&\circ&\circ\\ \circ&\circ&\circ&\circ\ar@{-}[u]\\ \circ&\circ\ar@{-}[r]&\circ\ar@{-}[r]&\circ\ar@{-}[u]\\ \circ\ar@{-}[r]&\circ\ar@{-}[u]&\circ&\circ} \qquad \item[a]ymatrix@R=4pt@C=4pt {\circ&\circ&\circ&\circ\\ \circ&\circ&\circ\ar@{-}[r]&\circ\ar@{-}[u]\\ \circ&\circ\ar@{-}[r]&\circ\ar@{-}[u]&\circ\\ \circ\ar@{-}[r]&\circ\ar@{-}[u]&\circ&\circ} [[/math]]

In fact, the number [math]C_n'[/math] of these paths is as follows, coinciding with [math]C_n[/math]:

[[math]] 1,1,2,5,14,42,132,429,\ldots [[/math]]

(8) So, here is our trick. We will prove on one hand that the numbers [math]C_n'[/math] satisfy the recurrence for the numbers [math]C_n[/math] that we want to prove, from (6), and on the other hand we will prove that we have [math]C_n'=C_n[/math]. Which is smart, isn't it. Getting to work now, in what regards our first task, this is easy, because when looking at where our path last intersects the diagonal of the square, we obtain the recurrence relation that we want, namely:

[[math]] C'_n=\sum_{k+l=n-1}C'_kC'_l [[/math]]

(9) In what regards now our second task, proving that we have [math]C_n'=C_n[/math], this is more tricky. If we ignore the assumption that our path must stay under the diagonal of the square, we have [math]\binom{2n}{n}[/math] such paths. And among these, we have the “good” ones, those that we want to count, and then the “bad” ones, those that we want to ignore.

(10) So, let us count the bad paths, those crossing the diagonal of the square, and reaching the higher diagonal next to it, the one joining [math](0,1)[/math] and [math](n,n+1)[/math]. In order to count these, the trick is to “flip” their bad part over that higher diagonal, as follows:

[[math]] \xymatrix@R=6pt@C=6pt {\cdot&\cdot&\cdot&\cdot&\cdot&\cdot\\ \circ&\circ&\circ&\circ\ar@{-}[r]&\circ\ar@{-}[r]\ar@{.}[u]&\circ\\ \circ&\circ\ar@{.}[r]&\circ\ar@{.}[r]&\circ\ar@{.}[r]\ar@{-}[u]&\circ\ar@{.}[u]&\circ\\ \circ&\circ\ar@{.}[u]&\circ&\circ\ar@{-}[u]&\circ&\circ\\ \circ&\circ\ar@{-}[r]\ar@{.}[u]&\circ\ar@{-}[r]&\circ\ar@{-}[u]&\circ&\circ\\ \circ&\circ\ar@{-}[u]&\circ&\circ&\circ&\circ\\ \circ\ar@{-}[r]&\circ\ar@{-}[u]&\circ&\circ&\circ&\circ} [[/math]]

(11) Now observe that, as it is obvious on the above picture, due to the flipping, the flipped bad path will no longer end in [math](n,n)[/math], but rather in [math](n-1,n+1)[/math]. Moreover, more is true, in the sense that, by thinking a bit, we see that the flipped bad paths are precisely those ending in [math](n-1,n+1)[/math]. Thus, we can count these flipped bad paths, and so the bad paths, and so the good paths too, and so good news, we are done.

(12) To finish now, by putting everything together, we have:

[[math]] \begin{eqnarray*} C_n' &=&\binom{2n}{n}-\binom{2n}{n-1}\\ &=&\binom{2n}{n}-\frac{n}{n+1}\binom{2n}{n}\\ &=&\frac{1}{n+1}\binom{2n}{n} \end{eqnarray*} [[/math]]

Thus we have indeed [math]C_n'=C_n[/math], and this finishes the proof.

■

As already mentioned, the binomial formula holds in fact for any exponent [math]a\in\mathbb Z/2[/math], after some combinatorial pain, and even for any [math]a\in\mathbb R[/math], but this is non-trivial, and the elementary study stops with Theorem 2.30. However, we will see in chapter 3 below that the problem can be solved, and in a very elegant way, by guess whom: calculus.

As another application of our methods, let us get now into the other version of the exponential function, namely [math]a^x[/math]. The idea is that some very interesting results appear with [math]a=e[/math], the number that we know from chapter 1. We first have:

Proposition

We have the following formula,

[[math]] \left(1+\frac{x}{n}\right)^n\to e^x [[/math]]

valid for any [math]x\in\mathbb R[/math].

Show Proof

We already know from chapter 1 that the result holds at [math]x=1[/math], and this because the number [math]e[/math] was by definition given by the following formula:

[[math]] \left(1+\frac{1}{n}\right)^n\to e [[/math]]

By taking inverses, we obtain as well the result at [math]x=-1[/math], namely:

[[math]] \left(1-\frac{1}{n}\right)^n\to\frac{1}{e} [[/math]]

In general now, when [math]\in\mathbb R[/math] is arbitrary, the best is to proceed as follows:

[[math]] \left(1+\frac{x}{n}\right)^n=\left[\left(1+\frac{x}{n}\right)^{n/x}\right]^x \to e^x [[/math]]

Thus, we are led to the conclusion in the statement.

■

Next, we have the following result, which is something quite far-reaching:

Theorem

We have the formula

[[math]] e^x=\sum_{k=0}^\infty\frac{x^k}{k!} [[/math]]

valid for any [math]x\in\mathbb R[/math].

Show Proof

This can be done in several steps, as follows:

(1) At [math]x=1[/math], which is the key step, we want to prove that we have the following equality, between the sum of a series, and a limit of a sequence:

[[math]] \sum_{k=0}^\infty\frac{1}{k!}=\lim_{n\to\infty}\left(1+\frac{1}{n}\right)^n [[/math]]

(2) For this purpose, the first observation is that we have the following estimate:

[[math]] 2 \lt \sum_{k=0}^\infty\frac{1}{k!} \lt \sum_{k=0}^\infty\frac{1}{2^{k-1}}=3 [[/math]]

Thus, the series [math]\sum_{k=0}^\infty\frac{1}{k!}[/math] converges indeed, towards a limit in [math](2,3)[/math].

(3) In order to prove now that this limit is [math]e[/math], observe that we have:

[[math]] \begin{eqnarray*} \left(1+\frac{1}{n}\right)^n &=&\sum_{k=0}^n\binom{n}{k}\cdot\frac{1}{n^k}\\ &=&\sum_{k=0}^n\frac{n(n-1)\ldots(n-k+1)}{k!}\cdot\frac{1}{n^k}\\ &\leq&\sum_{k=0}^n\frac{1}{k!} \end{eqnarray*} [[/math]]

Thus, with [math]n\to\infty[/math], we get that the limit of the series [math]\sum_{k=0}^\infty\frac{1}{k!}[/math] belongs to [math][e,3)[/math].

(4) For the reverse inequality, we use the following computation:

[[math]] \begin{eqnarray*} \sum_{k=0}^n\frac{1}{k!}-\left(1+\frac{1}{n}\right)^n &=&\sum_{k=0}^n\frac{1}{k!}-\sum_{k=0}^n\frac{n(n-1)\ldots(n-k+1)}{k!}\cdot\frac{1}{n^k}\\ &=&\sum_{k=2}^n\frac{1}{k!}-\sum_{k=2}^n\frac{n(n-1)\ldots(n-k+1)}{k!}\cdot\frac{1}{n^k}\\ &=&\sum_{k=2}^n\frac{n^k-n(n-1)\ldots(n-k+1)}{n^kk!}\\ &\leq&\sum_{k=2}^n\frac{n^k-(n-k)^k}{n^kk!}\\ &=&\sum_{k=2}^n\frac{1-\left(1-\frac{k}{n}\right)^k}{k!} \end{eqnarray*} [[/math]]

(5) In order to estimate the above expression that we found, we can use the following trivial inequality, valid for any number [math]x\in(0,1)[/math]:

[[math]] 1-x^k=(1-x)(1+x+x^2+\ldots+x^{k-1})\leq(1-x)k [[/math]]

Indeed, we can use this with [math]x=1-k/n[/math], and we obtain in this way:

[[math]] \begin{eqnarray*} \sum_{k=0}^n\frac{1}{k!}-\left(1+\frac{1}{n}\right)^n &\leq&\sum_{k=2}^n\frac{\frac{k}{n}\cdot k}{k!}\\ &=&\frac{1}{n}\sum_{k=2}^n\frac{k}{(k-1)!}\\ &=&\frac{1}{n}\sum_{k=2}^n\frac{k}{k-1}\cdot\frac{1}{(k-2)!}\\ &\leq&\frac{1}{n}\sum_{k=2}^n\frac{2}{2^{k-2}}\\ & \lt &\frac{4}{n} \end{eqnarray*} [[/math]]

Now since with [math]n\to\infty[/math] this goes to [math]0[/math], we obtain that the limit of the series [math]\sum_{k=0}^\infty\frac{1}{k!}[/math] is the same as the limit of the sequence [math]\left(1+\frac{1}{n}\right)^n[/math], manely [math]e[/math]. Thus, getting back now to what we wanted to prove, our theorem, we are done in this way with the case [math]x=1[/math].

(6) In order to deal now with the general case, consider the following function:

[[math]] f(x)=\sum_{k=0}^\infty\frac{x^k}{k!} [[/math]]

Observe that, by using our various results above, this function is indeed well-defined. Moreover, again by using our various results above, [math]f[/math] is continuous.

(7) Our next claim, which is the key one, is that we have:

[[math]] f(x+y)=f(x)f(y) [[/math]]

Indeed, by using the binomial formula, we have the following computation:

[[math]] \begin{eqnarray*} f(x+y) &=&\sum_{k=0}^\infty\frac{(x+y)^k}{k!}\\ &=&\sum_{k=0}^\infty\sum_{s=0}^k\binom{k}{s}\cdot\frac{x^sy^{k-s}}{k!}\\ &=&\sum_{k=0}^\infty\sum_{s=0}^k\frac{x^sy^{k-s}}{s!(k-s)!}\\ &=&f(x)f(y) \end{eqnarray*} [[/math]]

(8) In order to finish now, we know that our function [math]f[/math] is continuous, that it satisfies [math]f(x+y)=f(x)f(y)[/math], and that we have:

[[math]] f(0)=1\quad,\quad f(1)=e [[/math]]

But it is easy to prove that such a function is necessarily unique, and since [math]e^x[/math] obviously has all these properties too, we must have [math]f(x)=e^x[/math], as desired.

■

We will be back to all this, and to the logarithm and trigonometric functions as well, in chapter 3 below, when talking about derivatives and the Taylor formula.

General references

Banica, Teo (2024). "Calculus and applications". arXiv:2401.00911 [math.CO].